7
$\begingroup$

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.

$\endgroup$
6
  • 4
    $\begingroup$ This question is answered here: en.wikipedia.org/wiki/Primality_testing $\endgroup$
    – vadim123
    May 9, 2013 at 4:39
  • $\begingroup$ Thanks! That's gonna eat away at my weekend :) $\endgroup$
    – LearnIT
    May 9, 2013 at 4:44
  • $\begingroup$ You're welcome, have fun. $\endgroup$
    – vadim123
    May 9, 2013 at 4:45
  • 1
    $\begingroup$ @vadim123: You could make this an answer. I would upvote it $\endgroup$ May 9, 2013 at 4:45
  • $\begingroup$ @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. $\endgroup$
    – vadim123
    May 9, 2013 at 4:47

3 Answers 3

4
$\begingroup$
 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;
    }
  }
$\endgroup$
3
  • $\begingroup$ @LearnIT, this is in java $\endgroup$ May 9, 2013 at 5:33
  • $\begingroup$ 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! $\endgroup$
    – LearnIT
    May 9, 2013 at 6:08
  • $\begingroup$ @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. $\endgroup$ May 9, 2013 at 6:14
3
$\begingroup$

In Maple:

. x:= 124981242424:
  to 10 do x:= nextprime(x) end do;
$\endgroup$
1
  • $\begingroup$ Oh, I'm programming it in Java. I'm more curious as to the actual method. Vadim123 gave me a good link to read. $\endgroup$
    – LearnIT
    May 9, 2013 at 5:13
0
$\begingroup$

Unlike the other two answers, this answer tells you a way to do it in your head and you don't need knowledge of how to use any program for it. The problem of calculating the first 10 prime numbers after a given number is a different problem than the problem of calculating the sequence of all prime numbers in increasing order. I will first teach you how to calculate the sequence of all prime numbers in increasing order.

All natural numbers greater than 1 have the property that their second smallest factor is a prime number. If a natural number greater than 1 has no nontrivial prime factors, it has no nontrivial factors at all. Start with all the positive integers. If you cross out the multiples of 2, you get those that are not a multiple of 2. Any positive integer is odd if and only if 3 times that positive integer is odd. Now if you cross out the numbers that can be expressed as 3 times an odd number, you get those that are not a multiple of 2 or 3. All multiples of 4 are also a multiple of 2 so every positive integer that can't be expressed as a multiple of 2 or 3 can't be expressed as a multiple of 2, 3, or 4. Now for every positive integer, it can't be expressed as a multiple of 2, 3, or 4 if an only if 5 times that number can't be expressed as a multiple of 2, 3, or 4. Now if you cross out the numbers that can be expressed as 5 times a number that can't be expressed as a multiple of 2, 3, or 4, you get those that can't be expressed as a multiple of 2, 3, 4, or 5. All the multiples of 6 have already been crossed out. Now if you cross out all the numbers that can be expressed as 7 times a number that's not a multiple of 2, 3, or 5, you get the number that can't be expressed as a multiple of 2, 3, 5, or 7.

These numbers repeat with a cycle of length 210. That is precisely $6^3 - 6$. If you do this process in base 6, it won't be that hard to see the pattern. The numbers that are not a multiple of 2 or 3 are the ones congruent and 1 and 5 mod 6. The numbers that can be expressed as 5 times a number that is not a multiple of 2 or 3 repeat with a cycle of length 30 and the numbers that can be expressed as 7 times a number that is not a multiple of 2 or 3 repeat with a cycle of length 42. It's not that hard to figure out how to reliably generate the sequence of all the numbers from 1 to 210 that can't be expressed as a multiple of 2, 3, 5, or 7. Also note that when we are crossing out multiples of a prime number, the second multiple of that prime number to be crossed out is always the square of that prime number.

Now as you start crossing off more numbers in increasing order, to determine the next number to cross off, all you have to do is determine for each of the prime numbers from 11 to the one that's the square root of the next square of a prime number the next number that would be crossed off when you're crossing off multiples of that prime number if you were going one prime number at a time crossing off all the multiples of it that haven't been crossed off yet. Now you determine for which prime number the corresponding number to cross off is the smallest. Now that prime number is the only number whose corresponding number changes after you cross of its previous corresponding number. Now again, you can determine which of the corresponding numbers is the smallest and cross it off. Maybe you could even keep track of what the corresponding number for each prime number that has one is easily because it changes by only one number each time you cross off another number. Keep in mind that the corresponding prime number for each prime number that has one will always be that number times a prime number until the corresponding number for 11 is 1,331 so be careful to remember that 1,331 is one of the numbers that needs to be crossed off. When you're crossing off multiples of a prime number, you cross of the ones that can be expressed as that number times a number coprime to 210 that hasn't been crossed off after only crossing off multiples of smaller prime numbers.

For a really large number, determining from the start what the next 10 prime numbers are probably takes a similar length of time to determining what they are after you already generated all the prime numbers before it by the method I described. First you consider just the numbers that are coprime to 210. Next, all you have to do is determine for each prime number from 11 to the square root of the first square of a prime number after the given number what would be the first number after it to cross off when you're crossing off multiples of that prime number then cross of which ever is the smallest. Now its corresponding number is the only one that changes. Now you cross off the smallest of the current corresponding numbers. You keep going until there are 10 numbers after the given number that you have not yet crossed off and a number larger than all of them that you have crossed off.

Calculating all the prime numbers less than $11^2$ is even easier. I already stated a nice easy way to determine when a number is coprime to 210. It can easily be shown that $11^2 = (5 \times 11) + (6 \times 11) = 5^2 + (6 \times 5) + (6 \times 11) = ((6 \times 5) \times 4) + 1$.

$\endgroup$
2
  • $\begingroup$ In MATLAB, I believe there is an isprime() function so it could be done with a simple for loop and counter variable $\endgroup$
    – S J
    Jan 7, 2020 at 2:01
  • $\begingroup$ @SamuelVanderzee I intended this answer to give a way for people to do it in their head. I just fixed up my answer to say so. $\endgroup$
    – Timothy
    Jan 7, 2020 at 19:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .