Results 1 to 9 of 9

Thread: Prime: find prime number >N

  1. #1
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,531
    Thanks
    755
    Thanked 674 Times in 365 Posts

    Prime: find prime number >N

    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
    Attached Files Attached Files

  2. #2
    Member
    Join Date
    May 2012
    Location
    United States
    Posts
    330
    Thanks
    190
    Thanked 54 Times in 38 Posts
    Excellent! This can be very useful for many different things.

    Great job!

  3. #3
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,531
    Thanks
    755
    Thanked 674 Times in 365 Posts
    new version:
    • checks that number is odd
    • prints first divisor of the number specified in cmdline
    • 5x faster
    Attached Files Attached Files
    Last edited by Bulat Ziganshin; 5th March 2013 at 00:46.

  4. #4
    Member RichSelian's Avatar
    Join Date
    Aug 2011
    Location
    Shenzhen, China
    Posts
    164
    Thanks
    19
    Thanked 59 Times in 28 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    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?

  5. #5
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,531
    Thanks
    755
    Thanked 674 Times in 365 Posts
    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

  6. #6
    Member RichSelian's Avatar
    Join Date
    Aug 2011
    Location
    Shenzhen, China
    Posts
    164
    Thanks
    19
    Thanked 59 Times in 28 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    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:
    Code:
    #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;
    }

  7. #7
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 72 Times in 56 Posts
    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.

  8. #8
    Member Karhunen's Avatar
    Join Date
    Dec 2011
    Location
    USA
    Posts
    91
    Thanks
    2
    Thanked 1 Time in 1 Post
    How about using the result of known primes, as in http://en.wikipedia.org/wiki/Fermat_primality_test

  9. #9
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 72 Times in 56 Posts
    Quote Originally Posted by Karhunen View Post
    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.
    Last edited by nburns; 24th August 2013 at 01:30.

Similar Threads

  1. Euler's Number Triangle and Random Data
    By BetaTester in forum Data Compression
    Replies: 55
    Last Post: 19th February 2013, 05:02
  2. Replies: 41
    Last Post: 25th December 2012, 11:16
  3. Compression via Number Factorisation
    By MiY4Gi in forum Random Compression
    Replies: 14
    Last Post: 20th July 2012, 19:51
  4. rnd - simple pseudo random number generator
    By encode in forum Forum Archive
    Replies: 21
    Last Post: 14th January 2008, 03:41
  5. I cannot find jpegoptim win32 build
    By SvenBent in forum Forum Archive
    Replies: 2
    Last Post: 30th November 2007, 23:41

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •