# Seive of Atkin

Show 50 post(s) from this thread on one page
Page 1 of 2 12 Last
• November 25th, 2013, 05:37 PM
rockx
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; }```
• November 26th, 2013, 05:14 AM
VictorN
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).
• November 26th, 2013, 12:19 PM
Arjay
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
Paul McKenzie
Re: Seive of Atkin
Quote:

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 compile-time expression or constant.
Quote:

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
2kaud
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?

Quote:

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.
• November 26th, 2013, 02:48 PM
GCDEF
Re: Seive of Atkin
Quote:

Originally Posted by 2kaud
From where did you obtain this **** code?

http://thomasinterestingblog.wordpre...of-atkin-in-c/

• November 26th, 2013, 04:26 PM
2kaud
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.
• November 26th, 2013, 07:52 PM
rockx
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
2kaud
Re: Seive of Atkin
Quote:

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).
• November 27th, 2013, 08:49 AM
OReubens
Re: Seive of Atkin
Quote:

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
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.
• November 27th, 2013, 10:38 AM
2kaud
Re: Seive of Atkin
Quote:

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.
• November 27th, 2013, 04:14 PM
rockx
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
GCDEF
Re: Seive of Atkin
Quote:

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
2kaud
Re: Seive of Atkin
Quote:

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 super-computers do you have access?:eek:
• November 28th, 2013, 06:52 AM
OReubens
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 :)
Show 50 post(s) from this thread on one page
Page 1 of 2 12 Last