CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Member
Join Date
May 2004
Posts
249

## 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;
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. ## 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).

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.

4. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## 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 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. ## 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.

6. Elite Member Power Poster
Join Date
Nov 2003
Location
Florida
Posts
12,518

## Re: Seive of Atkin

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

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.

8. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## 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 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.

9. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## Re: Seive of Atkin

Originally Posted by OReubens
It is legal for some C compilers.
Yes. However that code has never been legal for Visual C++, and it has never been legal ANSI C++. Given that the question was posted in the Visual C++ forum, might as well point out that the code as-is will not compile.

Regards,

Paul McKenzie

10. Member
Join Date
May 2004
Posts
249

## 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

11. ## 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).

12. ## 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.

13. Member
Join Date
May 2004
Posts
249

## 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

14. Elite Member Power Poster
Join Date
Nov 2003
Location
Florida
Posts
12,518

## 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.

15. ## 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 super-computers do you have access?

#### Posting Permissions

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