Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As a practice applciation, I am trying to write a prime number calculator that would be able to given a number, for example "124981242424", determine the nearest prime number and give me the ten next prime numbers in increasing order.

I was trying to determine how to calculate primes and to my understanding a prime number is determined to be prime if it is not divisible by any previous prime numbers.

Therefore: 2,3,5,7,11... To calculate prime, we must divide all following numbers by the previous primes to determine the next prime, which in this case is 13.

This is the only method that I could think of that could be programmed.

Are there any other ways? Because this means my program would need to go back and calculate all the primes from the beginning to output the sequence that I want.

share|improve this question
2  
This question is answered here: en.wikipedia.org/wiki/Primality_testing –  vadim123 May 9 '13 at 4:39
    
Thanks! That's gonna eat away at my weekend :) –  LearnIT May 9 '13 at 4:44
    
You're welcome, have fun. –  vadim123 May 9 '13 at 4:45
1  
@vadim123: You could make this an answer. I would upvote it –  Ross Millikan May 9 '13 at 4:45
    
@Ross, thanks but I don't really care about reputation, and SE seems to discourage answers that are short and/or contain only a link. –  vadim123 May 9 '13 at 4:47

2 Answers 2

up vote 3 down vote accepted
 public class PrimalityTest {
   public static void main(String[] args) {
     long nearest = findNearest(124981242424L);
     System.out.println(nearest);

     long[] primes = nextPrimes(124981242424L, 10);
     System.out.println("Next 10 primes: ");
     for (int i = 0; i < primes.length; i++) {
         System.out.print(primes[i] + ",");
      } 
  }

  private static long[] nextPrimes(long num, final int count) {
    long[] primes = new long[count];
    int localCount = 0;
    for (long number = num;; number++) {
        if (isPrime(number)) {
            primes[localCount++] = number;
            if (localCount == count)
                break;
        }
    }
    return primes;
  }

  private static long findNearest(long num) {
    long nearestLarger = -1;
    for (long num2 = num;; num2++) {
       if (isPrime(num2)) {
            nearestLarger = num2;
            break;
        }
    }
    long nearestSmaller = -1;
    for (long num2 = num;; num2--) {
        if (isPrime(num2)) {
            nearestSmaller = num2;
            break;
        }
    }
    if (nearestLarger - num > num - nearestSmaller) {
        return nearestSmaller;
    }
    return nearestLarger;
  }

  public static boolean isPrime(final long num2) {
     if (num2 <= 3)
        return true;

     if ((num2 & 1) == 0)// check divisibility by 2
        return false;

     double sqrt = Math.sqrt(num2);
     for (long i = 3; i <= sqrt; i += 2)
        if (num2 % i == 0)
            return false;

      return true;
    }
  }
share|improve this answer
    
@LearnIT, this is in java –  lab bhattacharjee May 9 '13 at 5:33
    
Heh thanks for all the extra work. Didn't mean to have anyone actually write it! Negates my whole practicing bit lol, but no one can claim that you did not give the complete answer! –  LearnIT May 9 '13 at 6:08
    
@LearnIT, very few problems on earth have unique solutions. You are free to coin your own, may be better in performance, also optimize the one I have purveyed. –  lab bhattacharjee May 9 '13 at 6:14

In Maple:

. x:= 124981242424:
  to 10 do x:= nextprime(x) end do;
share|improve this answer
    
Oh, I'm programming it in Java. I'm more curious as to the actual method. Vadim123 gave me a good link to read. –  LearnIT May 9 '13 at 5:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.