Seive of Atkin
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Thread: Seive of Atkin

  1. #1
    Join Date
    May 2004
    Posts
    209

    Seive of Atkin

    What can be done to enhance this code. Like its gotta be bug free and efficient enough

    Code:
    #include <iostream>
    #include <cmath>
    #include <fstream>
    using namespace std;
    int main (int argc, char* argv[])
    {
     //Create the various different variables required
     int limit = 1000000;
     int root = ceil(sqrt(limit));
     bool sieve[limit];
     int primes[(limit/2)+1];
     int insert = 2;
     primes[0] = 2;
     primes[1] = 3;
     for (int z = 0; z < limit; z++) sieve[z] = false; //Not all compilers have false as the default boolean value
     for (int x = 1; x <= root; x++)
     {
     for (int y = 1; y <= root; y++)
     {
     //Main part of Sieve of Atkin
     int n = (4*x*x)+(y*y);
     if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true;
     n = (3*x*x)+(y*y);
     if (n <= limit && n % 12 == 7) sieve[n] ^= true;
     n = (3*x*x)-(y*y);
     if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true;
     }
     }
     //Mark all multiples of squares as non-prime
     for (int r = 5; r <= root; r++) if (sieve[r]) for (int i = r*r; i < limit; i += r*r) sieve[i] = false;
     //Add into prime array
     for (int a = 5; a < limit; a++)
     {
     if (sieve[a])
     {
     primes[insert] = a;
     insert++;
     }
     }
     //The following code just writes the array to a file
     ofstream file;
     char filename[100];
     sprintf(filename, "primes_%d.txt", limit);
     file.open(filename);
     for (int a = 0; a < insert; a++) file << primes[a] << ((a == insert-1) ? "" : "\n");
     file.close();
     cout << "Written to file.\n";
     return 0;
    }

  2. #2
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    17,421

    Re: Seive of Atkin

    First, use proper indentations withing the code snippet. Otherwise it is almost impossible to read/understand it.
    Second, what is this code for and why do you want to enhance it?
    Third, to make code "bug free" you have to design it good enough, then to debug and test it good enough.
    To make it efficient enough you first have to find out what part(s) of it take(s) to longest time(s).
    Victor Nijegorodov

  3. #3
    Arjay's Avatar
    Arjay is offline Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    11,309

    Re: Seive of Atkin

    Not sure the point to take a code snippet copied from the internet, and post it to a forum to ask for help to improve it.

  4. #4
    Join Date
    Apr 1999
    Posts
    27,431

    Re: Seive of Atkin

    Quote Originally Posted by rockx View Post
    What can be done to enhance this code.
    You can't enhance code that doesn't compile:
    Code:
     int limit = 1000000;
     int root = ceil(sqrt(limit));
     bool sieve[limit];
    That line that is colored in red is not legal C++ syntax. That code fails to compile using Visual Studio, and basically any ANSI C++ compiler.

    It is not legal to declare an array's size by using a variable (limit). An array's size must be a compile-time expression or constant.
    Like its gotta be bug free
    Well "bug free" it isn't, as it doesn't even compile.

    Regards,

    Paul McKenzie

  5. #5
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,460

    Re: Seive of Atkin

    There are other compile time problems apart from the one highlighted by Paul in post #4. Also, if you correct the compile problems there is then a run-time error of an unknown exception produced for the provided limit. From where did you obtain this **** code?

    Like its gotta be bug free
    It's definitely not!

    What is your requirement for prime numbers - as this topic has been covered several times on these forums.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  6. #6
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,108

    Re: Seive of Atkin

    Quote Originally Posted by 2kaud View Post
    From where did you obtain this **** code?
    http://thomasinterestingblog.wordpre...of-atkin-in-c/

    Weird thread.

  7. #7
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,460

    Re: Seive of Atkin

    I don't know how fast this Sieve Of Atkin program is supposed to be for generating prime numbers, but on my 2.4Ghz system my program generates prime numbers up to 10000000 in just under 5 seconds with a further 7 seconds to write all 664579 primes to a file.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  8. #8
    Join Date
    May 2004
    Posts
    209

    Re: Seive of Atkin

    so 2kaud, does ur program calculate prime numbers which has over 500 digits? i mean the really large ones?

    if so, could you please share the code

  9. #9
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,460

    Re: Seive of Atkin

    Quote Originally Posted by rockx View Post
    so 2kaud, does ur program calculate prime numbers which has over 500 digits? i mean the really large ones?

    if so, could you please share the code
    No it doesn't. Neither does the program you posted in post #1. The limit of the posted program is the size of the arrays that can be created on the stack (although the program could be changed to create them on the heap which would then have a maximum limit of the size of an unsigned int - but the posted program doesn't work properly anyhow). My prime program has the same limitation - max 4294967295.

    It would probably be possible to use type _UI64 (max 18446744073709551615) or possibly even type _UI128. But these wouldn't provide you with your requirement to calculate prime numbers which have over 500 digits.

    If you want to do things like this, you really, really need to use a proper large number library (and not my simple proof of concept one from an earlier post).
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  10. #10
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,925

    Re: Seive of Atkin

    That line that is colored in red is not legal C++ syntax. That code fails to compile using Visual Studio, and basically any ANSI C++ compiler.
    It is legal for some C compilers.


    Quote Originally Posted by 2kaud View Post
    I don't know how fast this Sieve Of Atkin program is supposed to be for generating prime numbers, but on my 2.4Ghz system my program generates prime numbers up to 10000000 in just under 5 seconds with a further 7 seconds to write all 664579 primes to a file.
    Actually, 5 seconds for the first 10mil primes is "slow" ;-)

    THe benefit of the Atkin sieve breaks down as soon as you have to deal with numbers that no longer fit into your integer types and you need to work with bigints.

    Then again, you typically tend to fall into a memory issue well before that point.

    Primes larger than about 2^30 on a 32bit system (and larger than about 2^38 on 64bit) will need a different approach than simple sieves entirely to still be fast enough.

    I have a prime routine that finds all primes up to 2^40 (1 terabyte) on Win32, not using disk storage (other than OS swapping) and does so in just under 2 hours on my "old" box. (Xeon E5430 at 2.66Ghz). that's technically 15 times faster than the 1-10mil in 5sec, although granted, it doesn't progress linearly.

    I'm assuming this routine can do about 2^50 before it runs out of memory (never bothered running it that long, 2^50 is 10000 times more than 2^40 so extrapolating linearly that would take 2000 hours, although realistically probably closer to 800ish). a Win64 with 32Gb version should be able to do up to 2^120 (if you want to grow a sizeable beard in the process)

    Note that even 2^120 would still "only" be a 36 digit number. I'm not sure how primes are efficiently calculated for those 500+ digit numbers.
    Last edited by OReubens; November 27th, 2013 at 09:13 AM.

  11. #11
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,460

    Re: Seive of Atkin

    Quote Originally Posted by rockx View Post
    calculate prime numbers which has over 500 digits? i mean the really large ones?
    Why do you want to calculate prime numbers this large? Do you want to know if a particular number is prime or do you want to generate a large number which is prime? Generating a large number which is prime is different to calculating primes up to a specified limit.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  12. #12
    Join Date
    May 2004
    Posts
    209

    Re: Seive of Atkin

    I simply want to calculate large prime numbers. The current world record sits at around 17.4 million digits. So using C++ i would like to device something which could get to at least the equivalent of that

  13. #13
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,108

    Re: Seive of Atkin

    Quote Originally Posted by rockx View Post
    I simply want to calculate large prime numbers. The current world record sits at around 17.4 million digits. So using C++ i would like to device something which could get to at least the equivalent of that
    Realistically, if your approach is to find code on the internet then post on a forum asking how to improve it, you're not likely to break any world records. You should probably take the time to learn the language first.

  14. #14
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,460

    Re: Seive of Atkin

    Quote Originally Posted by rockx View Post
    I simply want to calculate large prime numbers. The current world record sits at around 17.4 million digits. So using C++ i would like to device something which could get to at least the equivalent of that
    How many decades do you have in which to do this and to how many super-computers do you have access?
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  15. #15
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,925

    Re: Seive of Atkin

    Sieves are about finding a series of primes.

    There is another methodology to efficiently verify that a certain number is a prime or not.

    And there is yet another methodology to just generate a potential large prime.

    The current world record generated the prime very fast, actually verifying it is in fact prime was what took time. Note that most of these generated primes are one of many special forms of primes, the typical ones are mersenne primes (2n-1). the 17million digit one you speak of is one of these mersenne primes (257885161-1).

    I can generate a 2n-1 very fast (it's just a series of n 1 bits), verifying it's a prime would take me some time
    Last edited by OReubens; November 28th, 2013 at 06:58 AM.

Page 1 of 2 12 LastLast

Posting Permissions

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


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center