
November 25th, 2013, 05:37 PM
#1
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 nonprime
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 == insert1) ? "" : "\n");
file.close();
cout << "Written to file.\n";
return 0;
}

November 26th, 2013, 05:14 AM
#2
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

November 26th, 2013, 12:19 PM
#3
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.

November 26th, 2013, 02:27 PM
#4
Re: Seive of Atkin
Originally Posted by rockx
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 compiletime expression or constant.
Like its gotta be bug free
Well "bug free" it isn't, as it doesn't even compile.
Regards,
Paul McKenzie

November 26th, 2013, 02:42 PM
#5
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 runtime 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 the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/
C, C++ Compiler: Microsoft VS2017.2

November 26th, 2013, 02:48 PM
#6
Re: Seive of Atkin
Originally Posted by 2kaud
From where did you obtain this **** code?
http://thomasinterestingblog.wordpre...ofatkininc/
Weird thread.

November 26th, 2013, 04:26 PM
#7
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 the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/
C, C++ Compiler: Microsoft VS2017.2

November 26th, 2013, 07:52 PM
#8
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

November 27th, 2013, 05:41 AM
#9
Re: Seive of Atkin
Originally Posted by rockx
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 the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/
C, C++ Compiler: Microsoft VS2017.2

November 27th, 2013, 08:49 AM
#10
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.
Originally Posted by 2kaud
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 110mil 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.

November 27th, 2013, 10:38 AM
#11
Re: Seive of Atkin
Originally Posted by rockx
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 the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/
C, C++ Compiler: Microsoft VS2017.2

November 27th, 2013, 04:14 PM
#12
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

November 27th, 2013, 05:43 PM
#13
Re: Seive of Atkin
Originally Posted by rockx
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.

November 28th, 2013, 05:45 AM
#14
Re: Seive of Atkin
Originally Posted by rockx
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 supercomputers do you have access?
All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/
C, C++ Compiler: Microsoft VS2017.2

November 28th, 2013, 06:52 AM
#15
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 (2^{n}1). the 17million digit one you speak of is one of these mersenne primes (2^{57885161}1).
I can generate a 2^{n}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.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
OnDemand Webinars (sponsored)
