Prime Number Generator

[abachler]

OK, the contest is to generate 100 thousand unique Prime numbers from 2^32 to 2^64-1 in the shortest time possible. There are some limits of course.

1. You cannot load any values from external files.
2. Your entire program must be contained in a single cpp file of less than 64K named PrimeFunc.cpp with a function named PrimeFunc(__int64*) which will be called by the test program.
3. You may use no more than 10 'seed' values none of which may be greater than 2^32-1
4. All code must compile under visual studio 2008 express as a win32 console program. Default optimzation settings will be used.
5. All results must be placed into the __int64* array supplied by the test program.
6. You may not use any file or network access functions.
7. You may use inline assembly, OpenMP, threads, even the GPU as long as you limit GPU code to HLSL.
8. There can be no composite numbers returned
9. You must return exactly 100 thousand primes, no more no less.
10. Programs that crash are disqualified.
11. Programs that take more than 5 minutes to complete are disqualified.
12. Entries should be made public.
13. This contest is open ended so further optimizations should be submitted as a new entry.
14. (Optional)The solution should be general enough so that it could in theory be applied to build a comprehensive list of all primes.
15. You may not include any header files other than <math.h>, some exceptions may be made to this ask first.

The test system is a Pentium 4HT 3.2 GHz with 2GB of 800MHz dual channel memory. The GPU is an 8600 with 1GB of ram. A non-optimized test program was run and completed within the alloted time.

[Daved]

How will you be verifying the correctness of the returned values?

[whiteflags]

>> 3. You may use no more than 10 'seed' values none of which may be greater than 2^32-1

Does it not make sense to start from the first number in the range you require?

[abachler]

the test program will verify the values in the array after the PrimeFunc() returns.. It will test every value both for uniqueness and for primality.

The testing phase of the program is not counted against the runtime of the function.

Starting from 2^32+1 is fine, since it is not prime. By seed value I mean specifically prime numbers or precalculated values used to circumvent doign the actual calculations. Some algorithms require seedign with known primes to operate efficiently, so I allow the use of 10. The rule is to prevent someone from just writing a huge array with all the values and returnign it.

[zacs7]

Do we have to write it in C++?

[abachler]

Originally Posted by zacs7

Do we have to write it in C++?

as stated, you can also use inline assembly or HLSL. No C# python or java if thats what you mean.

here is an example of one possible solution.

[hauzer]

I think he wanted to ask can we do it in plain C.
2. - Can't we use unsigned long long instead of int64? I'm somehow safer with it.
4. - Why not use mingw? And what's with the optimizations?

[Nor]

RSA Encryption
Your Going Down baby

[abachler]

Originally Posted by hauzer

I think he wanted to ask can we do it in plain C.
2. - Can't we use unsigned long long instead of int64? I'm somehow safer with it.
4. - Why not use mingw? And what's with the optimizations?

yeah plain C is fine.

you can recast the function call internally if you want, but the test program is already written and the test procedure will just invovle drag drop compile and run.

void YourFunc(long long*);
 
void PrimeFunc(__int64* blah){
   YourFunc((long long*) blah);
   return;
   }
 
void YourFunc(long long* blah){
   return;
   }

is fine

and im not using mingw because I use VS. I stated what compiler so that you know what compiler specific extensions you can and cant use.

The default optimizations on my compiler are compile for speed and it uses the static multithreaded runtimes if thats important, it shouldnt be.

[Nor]

Where do we need to send our entrys?

[abachler]

just post them here, its an open ended contest, so no need to keep secrets

[zacs7]

Can we use the network card, if you catch my drift? :-)

[hauzer]

@abachler: Ok, all good.

[abachler]

Originally Posted by zacs7

Can we use the network card, if you catch my drift? :-)

Sure as long as you follow rule #1 and #6, by all means use teh PIC on the NIC to crunch numbers

and good luck accessign it without breakign rule #15 or #2 part b

oh as far as teh earlier statement that plain C is ok, its OK as long as it will compile as C++ code. So make sure you use explicit recasts. Im not going to edit your code to get it to compile.

[laserlight]

Originally Posted by abachler

2. Your entire program must be contained in a single cpp file of less than 64K named PrimeFunc.cpp with a function named PrimeFunc(__int64*) which will be called by the test program.
5. All results must be placed into the __int64* array supplied by the test program.

Instead of __int64, I suggest that you go with something like sqlite3_int64.

Originally Posted by abachler

15. You may not include any header files other than <math.h>, some exceptions may be made to this ask first.

In C++ that should be <cmath>. Actually, why not just allow the C and C++ standard libraries?