Prime: find prime number >N

[Bulat Ziganshin]

i just wrote small program that prints smallest prime larger than N. meanwhile it also prints nonprime numbers that don't have deividers less than 1000. program transcript:

C:\>gcc -O2 prime.cpp

C:\>t a.exe 1112223334445556667
1112223334445556667
1112223334445556682 / 39509
1112223334445556701 / 7640263
1112223334445556703 / 550208699
1112223334445556719 is prime!!!

Elapsed time = 31.840 seconds


C:\>t a.exe 11122233344455566678
11122233344455566678
11122233344455566679 is prime!!!

Elapsed time = 68.262 seconds

[comp1]

Excellent! This can be very useful for many different things.

Great job!

[Bulat Ziganshin]

new version:

• checks that number is odd
• prints first divisor of the number specified in cmdline
• 5x faster

[RichSelian]

new version:

• checks that number is odd
• prints first divisor of the number specified in cmdline
• 5x faster

The complexity seems to be O(sqrt(n)*log(n)), when n > 1e+16 it becomes slow.
How about using some Monte Carlo method to skip most non-primes?

[Bulat Ziganshin]

i wonder why log(n) here? i just enumerate all odd numbers less than sqrt(n). with about 10 seconds for one N in the worst case and 0.01 seconds for 32-bit N, this algo is fast enough for my needs

[RichSelian]

i wonder why log(n) here? i just enumerate all odd numbers less than sqrt(n). with about 10 seconds for one N in the worst case and 0.01 seconds for 32-bit N, this algo is fast enough for my needs

a big number n has a probability of (1/logn) to become a prime, so you are expected to test 0.5logn numbers before you find it. but i'm not sure that test a len=log(n) sequence numbers need O(log(n)*sqrt(n)) because not all numbers need sqrt(n) to test.

add here is a even faster implement, skipping multiple of 2, 3, 5:

#include <cstdio>
#include <cmath>
#include <algorithm>


using namespace std;


int main(int argc, char** argv) {
    unsigned long long n;
    unsigned long long m;
    unsigned long long i;
    int is_prime = 0;


    sscanf(argv[1], "%llu", &n);


    if(n <=  2) return printf("%d is a prime.\n",  2), 0;
    if(n <=  3) return printf("%d is a prime.\n",  3), 0;
    if(n <=  5) return printf("%d is a prime.\n",  5), 0;
    if(n <=  7) return printf("%d is a prime.\n",  7), 0;
    if(n <= 11) return printf("%d is a prime.\n", 11), 0;
    if(n <= 13) return printf("%d is a prime.\n", 13), 0;
    if(n <= 17) return printf("%d is a prime.\n", 17), 0;
    if(n <= 19) return printf("%d is a prime.\n", 19), 0;
    if(n <= 23) return printf("%d is a prime.\n", 23), 0;
    if(n <= 29) return printf("%d is a prime.\n", 29), 0;
    n += (n % 2 == 0);


    while(!is_prime) {
        if(n %  3 == 0 || n % 17 == 0) {n += 2; continue;}
        if(n %  5 == 0 || n % 19 == 0) {n += 2; continue;}
        if(n %  7 == 0 || n % 23 == 0) {n += 2; continue;}
        if(n % 11 == 0 || n % 29 == 0) {n += 2; continue;}
        if(n % 13 == 0)                {n += 2; continue;}


        m = sqrt(n) + 10;
        is_prime = 1;


        for(i = 30; i < m; i += 30) {
            if(     n % (i +  1) == 0 || n % (i +  7) == 0 || n % (i + 11) == 0 ||
                    n % (i + 13) == 0 || n % (i + 17) == 0 ||
                    n % (i + 19) == 0 || n % (i + 23) == 0 || n % (i + 29) == 0) {
                is_prime = 0;
                break;
            }
        }


        if(is_prime) {
            printf("%llu is a prime.", n);
            return 0;
        }
        n += 2;
    }
    return 0;
}

[nburns]

There are a lot of number theoretic algorithms on Daniel Bernstein's website, many with implementations (http://cr.yp.to/djb.html).

If Bulat's simple prime number algorithm runs fast enough for its intended purpose, e.g. 32-bit integers, then anything more would be overkill.

[Karhunen]

How about using the result of known primes, as in http://en.wikipedia.org/wiki/Fermat_primality_test

[nburns]

How about using the result of known primes, as in http://en.wikipedia.org/wiki/Fermat_primality_test

It would probably be overkill, since Bulat's algorithm is for small numbers and it's intended to be used off-line. That test might be an improvement if you had to choose one in real time. That test also has a chance of false positives.

You could test multiple prime divisors at one time if you computed their product and found the GCD of this number and the candidate. There are fast algorithms for GCD.

This is the type of problem where, even if you have a great idea, it's virtually certain to be already known about. I try not to think too hard about these.