find the nth prime prime number - Page 2

[cse.avinash]

yep this is the same thing , I beleif and so Its me a week to solve this question, I learned a lot from this questions, read seives algo and redefines it to work fast, but it still increasing the time.
I think, I need to apply segmentation over a range only
see -> accessing a is very expensive in array if i is very large
so I need to minimize this access time. thats my new work to do for this problem.

[Adak]

I agree that we'll both learn a lot.

But I disagree with you on the access times for large indexes in an array. Arrays have random access, so access to any index, large or small, is simply a matter of 1 addition. It's true that on large arrays, you may find some of the array is not in cache (fast) memory, but still, the access for a low number will be the same as the access time for a much higher number IF both parts of the array are in the same part of memory.

Here's a good read if you have a bit of math background (I don't but fake it):
http://www.ams.org/journals/bull/2005-42-01/S0273-0979-04-01037-7/S0273-0979-04-01037-7.pdf

I'm wondering if the contest doesn't count the time it takes to print out all the requests? I've seen some solve times in there that were less than a second! Clearly, I don't understand all the rules here.

[Smeagel13]

Forget the work one, that's dog slow now...

My new times on a crappy Core 2 Quad about 2 years old :

Find all primes in a million, 0.177 seconds.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

unsigned long * g_prime;
unsigned long   g_prime_ndx = 0ul;

int is_prime(const unsigned long test) {

	unsigned long ndx;
	unsigned long sqr = (unsigned long) sqrt(test);

	for(ndx = 0ul; (ndx <= g_prime_ndx) && (g_prime[ndx] <= sqr); ndx++) {

		if((test % g_prime[ndx]) == 0.0) {

			return 0;

		}

	}

	return 1;

}

int main(int argc, char * argv[]) {

	unsigned long ndx;
	unsigned long max_number;

	if(argc != 2) {

		printf("Usage: primes <max-number>\n");
		return 0;

	}

	max_number = (unsigned long) atoll(argv[1]);
	g_prime = (unsigned long *) malloc(sizeof(unsigned long) * (max_number / 2));
	g_prime[0] = 2ul;

	for(ndx = 3ul; ndx <= max_number; ndx += 2ul) {

		if(is_prime(ndx)) {

			g_prime[++g_prime_ndx] = ndx;

		}

	}

	// Counter always 1 behind for array index.
	printf("Found %u primes.\n", ++g_prime_ndx);

	return 0;

}

I changed it to find the one millionth prime and it took 6.3 seconds, with some of the Smeagel plan I'll get that down.

[Smeagel13]

@Smeagel, I haven't worked with this yet, but I've seen this mentioned on a web site on primes. Is this OK or dodgy?

Truthfully, I don't know, haven't tested it yet ...

The problem is once we have the start number we also need an nth number to start with or the nth number will be displaced by a lot.

[Adak]

That looks fast!

What algorithm is that called?

I'm reading just now on the AKS primality algorithm, and the author (url noted just above this in my previous post), notes several other techniques to test for primality.

I can make up a nth primes array file if you like - any gap is fine. CSE was noting that due to a size limit, we need to keep the array sized for Goldilocks (@CSE: "Goldilocks" means that it's not too big and not too small, just right).

[Smeagel13]

Goldilocks .. haha, I like it!

I wrote it a while back and cleaned it up just now ... so no name.

To be fair, it's the same algorithm as yours (composite number laws and square roots) just wrote in a different way. I think if you stripped out some of those reset assigns you could speed it up but only marginally.

Have a look at Sieve of Atkin http://cr.yp.to/primegen.html

[Adak]

I looked at primegen, but it's not a simple program - it has 80, yes no shit, 80! files, in total.

I'll take a peek at Atkins Sieve in Wikipedia, but Bernstein's primegen code is WAY out of my league, being loaded with bit operations and even assembly. <shudder>.

[Adak]

I'm working with Atkins Sieve (after a brief interest in Sieve of Sundaram which turned out to be the slowest Sieve of them all < naturally! :( > ).

For your program Smeagel, can you give it this test:

Make a list up of every 100th prime (or whatever gap size seems best to you), and load it into the array of primes, up to the five million upper limit.

Then generate queries in the average size of 2,250,000 as the kth prime number request. The time for that will show us if we have a chance with the program, as is. As the numbers get bigger, we know the times will get longer - but by how much?

I'm starting to wonder if this problem is really about *finding* the primes very fast, OR is it about *storing* the list of all primes, in a more compact way, for fast retrival?

Hmmm...

Well, first things first, I'm back to Atkins Sieve, and our Smeagel plan. ;)

[Adak]

@CSE.avinash:
Your program has too many zeroes in the size of the array! You should only have SIX zeroes in the size of your array, not eight.

As it turns out, the Sieve of Eratosthenes is faster than any of the other sieve prime number generators unless you optimize the others. I ran one against the new Sieve of Atkins I just coded up (with huge pseudo code help from Wiki), and it was actually faster than Atkins' Sieve, by a hair, going up to a max of 5 million.

I know with some optimizing, I can bring down the times on Sieve of Atkins', but I believe we can use the Sieve of Eratosthenes, just as well. Smeagel, I'd like to see the test times of your program handling 50,000 Queries, with an average kth of 2,500,000. I know I gave you the wrong number before. Brain not working! ;)

We can compare that with the Sieve of E. program CSE brought in, and see how they compare in that same 50,000 query test, if Smeagel has the time to test CSE's program, also. I'd do it, but it should be done on the same system to be meaningful.

@CSE: what size of array for holding primes would you recommend? I'll make up whatever size you want to try out for some testing. Maybe 10,000 would be OK? Better would be 25,000 or more, but what is the largest array you can use in the test?

We have a very fast prime number generator program now, (and some fast one's that are just not fast enough for this insane test).

I'll look over your Sieve of Eratosthenes program CSE, and see if there's anything we can optimize more on it, OK? I studied the fast program that Diwakar linked to and any optimizations are easily made.

Let me know how you feel about the above, OK?

[D33wakar]

I studied the fast program that Diwakar linked to and any optimizations are easily made.

In that particular program, I changed the following line:

for (i=2; i*i <= size; i++) {

to

int k;
for (i=2,k=1; i*i <= size; i=k*2+1,k++)

so that 'i' would only be an odd value(ignoring all evens), but it didn't affect the prime generation time much.So, I guess that wouldn't be an optimization(as the definition goes).Also I'm thinking, in the second loop statement

for(j = i+i; j < size; j+=i)

how about initializing as 'j=i*i' .
And also ignoring multiples of previous values of i.

for e.g. 
when i=2,j becomes4,6,8,10,12,14,16,18...< size
when i=3,j becomes 6,9,12,15,18,21,24...<size
when i=5,j become 10,15,20,25,30,35,40,45..<size
when i=7,j becomes 14,21,28,35,42,56...<size
Did you see the redundancy? I have not yet figured out how to solve that, but will that make a difference in the speed of the program?

What were your optimizations on that code Adak?

[Adak]

I didn't optimize the S of E program yet. I was working on the S of Atkin. I studied and tested B's S of E program that you linked to (the fast one without the goto), and it was REALLY fast.

Galway has a doctoral thesis on the subject, and mentions that S of A is faster than S of E, only at the larger numbers (10^10 or so).

So what I meant optimizing was CSE's S of E program, if it needed it, to match the performance of B's S of E program. I'm getting some incredibly fast times with that program - 0.015 seconds for primes less than 5 million!

The Sieve of Atkin program I coded up is at 0.034, in comparison, so it's twice as slow, currently. (It is taken from the pseudo code in Wikipedia, which states right up front that it is a straightforward design, but not an optimized one.) I've made a few improvements to get it down to 0.034 seconds, but I'm quite happy to go with any program that is this fast, including Smeagel's program.

Everything depends on how the program works in the 50,000 query test with values averaging 2,500,000 - that's the acid test, and should approximate the actual website test it will receive there.

Sorry if I gave you the impression I was going to optimize B's Sieve of E program. I meant the S of E program that CSE posted (which I have barely studied at all yet).

[Smeagel13]

The fastest times must be coming straight out of an array.

I've just tweaked my program to learn the primes, and then if it's given an nth that it already knows about it reads it from the array.

The problem is that if the nth numbers start small and go up it's fast, each increment takes small amount of time. But if the nth number is huge to start with it takes a blow finding that, for example the 4,931,941th prime and then every next nth number is pretty much in the known numbers and finding those takes nothing.

For 50k numbers i'm getting around 65 seconds (of which 65 seconds is spent on finding that 4,931,941th prime) - my first stab at that, but they must be reading them from a pre-populated array at compile time.

0.015 seconds for primes less than 5 million!

That is fast, much more than mine. Don't want to sound harsh, but does it find the correct results? My 4,931,941th prime is wrong according to http://primes.utm.edu/lists/small/millions/

[Adak]

I haven't checked the fast program out, beyond the first and last row of primes less than 1,000. I've been working on Sieve of Atkin, and got it working, but it's slower than the Sieve of Eratosthenes version.

I'll have to code up a checker. I have a list of all the primes, but only up to a million. I'll have to get the bigger list of 'em.

Unfortunately, that sounds like a "red card" for your program, with this challenge, but my trial division program was getting lonely on the sidelines. ;)

There are a few unanswered questions about this challenge, but I don't want to look up any solutions for it (well I kinda do, but no). That would be seeing the last 15 minutes of the movie thriller, before you see the rest of it -- buzz kill!

I'll get some testing code up and running to verify the primes we're generating. Got to do it early because The Walking Dead will be visiting me, tonight! ;)

Why are Zombies so creepy? ;)

Thanks for trying on that program. If you can think of any way to get it back on the playing field, by all means, feel free! The more the merrier, if they're fast enough.

Yeah, I'm wondering about the 10 seconds, handling 50K queries? This may not have anything to do with generating primes at all, but be about efficient bit packing and probing to get the answers.

[D33wakar]

Yeah, I'm wondering about the 10 seconds, handling 50K queries? This may not have anything to do with generating primes at all, but be about efficient bit packing and probing to get the answers.

Yeah I think so, 'cause the time taken to generate the primes(up to 50000000)and store them in an array is taking a lot less(less than 4 seconds with the program I'm working on), but displaying them all will take a lot of time.I guess the same is with the cse's code.What about your 'Sieve of Atkin'? So according to the challenge,

The problem statement is really simple. There are some queries. You are to give the answers.
Input

An integer stating the number of queries Q(equal to 50000), and Q lines follow, each containing one integer K between 1 and 5000000 inclusive.
Output Q lines with the answer of each query: the Kth prime number.
Example

Input:
8
1
10
100
1000
10000
100000
1000000

Output:
2
29
541
7919
104729
1299709
15485863

We have to display only those primes which are in the query. Is that the correct interpretation of the challenge?

Why are Zombies so creepy?

They aren't! I think they are nice creatures just longing for human flesh and often forget to brush their teeth.And aw there little walk, so cute!

[cse.avinash]

@Adak , @Smeagel and @Diwakar thanks for replying ..:)
Sorry I was out of touch with my lappy and net for 2 days so I couldn't do any research .

Yes Seives of atkin is the improved version of S.O.E and is a faster approach. I have looked it before but I didn't use that algo as I want to optimise seive of E's algo .

About the size of array , its better to use dynamic memory allocation and character array to store the element as it will decrease the memory usage to great extent.

I also tried to redirect all the 5000000 prime numbers into a file , and store all the prime numbers in an array, but after redirecting the file is not responding..:(

I tried to use this algo:--

for(i=3;i<=MAX;i+=2)  //skip even numbers
{
   if(arr[i]==0)  //if it is not marked..=>prime
   {
        for(j=i*i, k=i<<1; j<MAX; j+=k)  //mark all it's multiples
            arr[j]=1;
   }
}

@Smeagel :

Forget the work one, that's dog slow now...

My new times on a crappy Core 2 Quad about 2 years old :

Find all primes in a million, 0.177 seconds.

for input 3000000 your code is taking 2.69 seconds in my core i3 processor while my code is taking 0.208 seconds check it change the value of num to 3000000 in my code.

@Adak : I have not yet studied AKS algo but interested in atkins algo, its the final way to achieve success.

@Diwakar :

so that 'i' would only be an odd value(ignoring all evens), but it didn't affect the prime generation time much.So, I guess that wouldn't be an optimization

It should work diwakar, as you are reducing the checking of numbers to half .

Yep there is some redundancy , debug the code hope you'll get it out, I will also try to debug that code, as its the fastest approach till now.

Why you all don't check for segmented seive of E. ??

[Adak]

@Diwakar:
Yes, they give you the number of queries to process, and then each number they give you, you have to find that kth number of prime number, and print it. In one test we did, it took a little less than four seconds just to print up 50,000 numbers.

But we may have this wrong. Maybe the queries vary in number, if they're always going to give you 50,000 queries, why the number telling you how many queries you'll be given? Maybe if you are given higher k numbers, you get fewer queries? That would make sense, and make it possible to win this challenge.

This is the Sieve of Atkin I coded up from the Wikipedia pseudo code for it. It is fast, but not as fast as the Sieve of Eratosthenes, with the same level of optimization. If you get down to using bit shifting and Fast Fourier Transform multiplication, then SofA becomes a bit faster than SofE. That is not something I'm going to do for this, however.

IMO, any program as fast as the SofE program, is fast enough.

Here's the Sieve of Atkin program, but it has not been checked for accuracy thoroughly.

#include <stdio.h>
#include <math.h>
#include <time.h>

#define MAX 1000

char sieve[MAX+1];

int main(void) {
   unsigned int x, y=1, i, k, n, root;
   clock_t start, stop;

   start = clock();
   root = sqrt(MAX)+1;

   for(x=1;x<root;x++) {
      for(y=1;y<root;y++) {
         n=(4*(x*x)) + y*y;
         if((n<MAX) && (n % 12 == 1 || n % 12 == 5)) {
            sieve[n] = !sieve[n];
         }
         n=(3*(x*x)) + y*y;
         if((n<MAX) && (n % 12 == 7)) {
            sieve[n] = !sieve[n];  
         }  
         n =(3*(x*x)) - y*y;
         if((x>y) && (n<MAX) && (n % 12 == 11)) {
            sieve[n] = !sieve[n];
         }
      }
   }
   for(n=5;n<root;n++) {
      if(sieve[n]) {
         for(i=1,k=n*n;k<MAX;i++) {
            k=i*(n*n);
            if(k>MAX) break;
            sieve[k]=0;
         }
      }
   }
   
   printf("%8d  %8d  ",2,3);
   
   for(n=5;n<MAX;n++) { if(sieve[n]) printf("%8d  ",n); }
   
   stop = clock() - start;
   i = checkIt();
   
   printf("\n\nTime was %f seconds\n", (double) stop/CLOCKS_PER_SEC);
   putchar('\n');
   return 0;
}

Another problem with SofA is the multiplication - it's only going to get worse, if you decide to look for larger primes. Say for another challenge. So in my opinion, it's a less useful algorithm, best suited to academia.

[Adak]

For comparison, look at these two programs, both Sieve of Eratosthenes (SoE). The first is a simple, short and well designed program. The second one uses every trick in the book (wheel, gaps array, bit level logic), and is three times bigger than the first one, but slower. ;)

The first one is faster - always (tested only to 5 million however). If there were to be an error in the program, the first one would be easy to fix. The second one would be much more difficult to debug.

How fast is the first program? Blazing fast! How about 0.19 seconds for 5 million primes (not checked yet for accuracy though).

Try them on your system, and see what you think. For me, the first one is the fastest I've tested so far, AND it's one of the easiest and shortest.

Clearly a winner.

P.S. As it turns out, another reason that Sieve of Atkin was so fast, in the well known PrimeGen program, was that the code had tables of many primes, explicitly included in arrays!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 5000000

void getPrimes(void) {
   unsigned int i,j;
   char *sieve = calloc(MAX, 1);
   for (i=2; i*i <= MAX; i++) {
      if (!sieve[i]) {
         for(j = i+i; j < MAX; j+=i) 
            sieve[j] = 1;
      }
   }
   //for (i=2; i<MAX; i++) { if (!sieve[i]) { printf("%8d  ", i); }  } 
   free(sieve);
}
int main() {
   clock_t start,stop;
   start = clock();
   getPrimes();
   stop = clock() - start;
   printf("\n\nElapsed time: %f seconds\n",(double)stop/CLOCKS_PER_SEC);
   
   return 0;
} 
/*
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

#ifdef __LP64__
     #define LONGSIZE 8
     #define SHIFT 6
     #define MASK 63
#else
     #define LONGSIZE 4
     #define SHIFT 5
     #define MASK 31
#endif

//#define PRINTPRIMES     // Print a list of the primes
//#define PRINTCOUNT      // Print a count of the primes
#define PRINTTIME       // Print the computation time

static int smallprimes[14] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43};

int main(int argc, char** argv)
{    clock_t starttime = clock();
     double totaltime;
     long i, j, n, p, s, ps, gapslen, last, primorial=1, total=0;
     long* starting;
     long* primes;
     unsigned char* gaps;
     long* pgaps;

     if(argc>1)
          n = atol(argv[1]);
     else
     {    fprintf(stderr, "No input\n");
          exit(1);
     }

     if(n<1)
     {    fprintf(stderr, "Invalid input\n");
          exit(1);
     }
     // Easy case
     else if(n<43)
     {    totaltime = (double)(clock()-starttime)/CLOCKS_PER_SEC;
          #ifdef PRINTPRIMES
          for(i=0; smallprimes[i]<=n; i++)
               printf("%u\n", smallprimes[i]);
          #endif
          #ifdef PRINTCOUNT
          for(i=0; smallprimes[i]<=n; i++);
          printf("Primes: %lu/%lu\n", i, n);
          #endif
          #ifdef PRINTTIME
          printf("Computation: %.2f seconds\n", totaltime);
          #endif
          return 0;
     }

     // Setup
     for(i=0; i<14; i++)
          if(smallprimes[i]*primorial<n/log(n))
          {    primorial *= smallprimes[i];
               total++;
               #ifdef PRINTPRIMES
               printf("%u\n", smallprimes[i]);
               #endif
          }
          else
               break;

     // Allocate memory for starting array
     starting = (long*)malloc(((primorial>>SHIFT)+1)<<(SHIFT-3));
     if(starting==NULL)
     {    fprintf(stderr, "No memory for starting array.\n");
          exit(1);
     }
     memset(starting, 255, ((primorial>>SHIFT)+1)<<(SHIFT-3));

     // Simple Eratosthenes on starting array
     for(i=0; i<total; i++)
          for(j=smallprimes[i]-1; j<primorial; j+=smallprimes[i])
               starting[j>>SHIFT] &= ~(1l<<(j&MASK));

     // Allocate memory for prime array
     primes = (long*)calloc((n>>SHIFT)+1, LONGSIZE);
     if(primes==NULL)
     {    fprintf(stderr, "No memory for prime array.\n");
          exit(1);
     }

     // Allocate memory for gaps array
     gapslen = n/smallprimes[total]+1;
     gaps = (unsigned char*)malloc(gapslen+1);
     if(gaps==NULL)
     {    fprintf(stderr, "No memory for gaps array.\n");
          exit(1);
     }

     // Construct wheel
     last = 0;
     for(i=primorial-1; i>=0; i--)
          if(starting[i>>SHIFT]&(1l<<(i&MASK)))
          {    if(last==0)
               {    gaps[i+1] = primorial-i;
                    gaps[last] = primorial-i;
               }
               else
               {    gaps[i+1] = last-i;
                    gaps[last] = last-i;
               }
               last = i;
          }
     free(starting);

     // Roll wheel
     j = 0;
     for(i=0; i<n; i+=gaps[j])
     {    primes[i>>SHIFT] |= 1l<<(i&MASK);
          j += gaps[j+1];
          if(j==primorial)
               j = 0;
     }

     // Complete gaps array
     last = 0;
     for(i=gapslen-1; i>=0; i--)
          if(primes[i>>SHIFT]&(1l<<(i&MASK)))
          {    if(last!=0)
               {    gaps[i+1] = last-i;
                    gaps[last] = last-i;
               }
               last = i;
               if(i<primorial)
                    break;
          }

     // Sieve with primes up to sqrt(n)
     for(p=gaps[1]+1; p*p<=n; p+=gaps[p])
     {    // Calculate pgaps for powers of two
          pgaps = (long*)calloc(256, LONGSIZE);
          pgaps[1] = p;
          for(j=2; j<256; j<<=1)
               pgaps[j] = pgaps[j>>1]<<1;

          // Find initial s
          gapslen = n/p-1;
          for(s=gapslen; !(primes[s>>SHIFT]&(1l<<(s&MASK))); s--);
          ps = p*(s+1)-1;

          // Run over all s
          while(s>=p-1)
          {    // Remove composite p*s from primes array
               primes[ps>>SHIFT] &= ~(1l<<(ps&MASK));

               // Update gaps array if necessary
               if(ps<gapslen)
               {    gaps[ps-gaps[ps]+1] += gaps[ps+1];
                    gaps[ps+gaps[ps+1]] += gaps[ps];
               }

               // Find next s
               s -= gaps[s];

               // Find required pgap
               if(pgaps[gaps[s+1]]==0)
                    for(j=0; (gaps[s+1]>>j)!=0; j++)
                         if((gaps[s+1]>>j)&1)
                              pgaps[gaps[s+1]] += pgaps[1<<j];

               // Find next ps
               ps -= pgaps[gaps[s+1]];
          }
          free(pgaps);

          total++;
          #ifdef PRINTPRIMES
          printf("%lu\n", p);
          #endif
     }

     // Finished computing
     totaltime = (double)(clock()-starttime)/CLOCKS_PER_SEC;
     free(gaps);

     #if defined(PRINTPRIMES)||defined(PRINTCOUNT)
     // Enumerate the primes
     for(i=p-1; i<n; i++)
          if(primes[i>>SHIFT]&(1l<<(i&MASK)))
          {    total++;
               #ifdef PRINTPRIMES
               printf("%lu\n", i+1);
               #endif
          }
     #endif
     free(primes);

     #ifdef PRINTCOUNT
     printf("Primes: %lu/%lu\n", total, n);
     #endif
     #ifdef PRINTTIME
     printf("Computation: %.2f seconds\n", totaltime);
     #endif

     return 0;
}
*/

[D33wakar]

Alright guys, I registered in to that site and submitted the following code, but it didn't accept the code as a valid answer.The time taken by the code I submitted was 1.23 as shown in the site.

#include <stdio.h>
#include <stdlib.h>
#define SIZE 50000000
int arr[SIZE]={0};

void sieve(int size) {
       int i,j,k;
       char *sieve = calloc(size, 1);
       for (i=2,k=1; i*i <= size; i=k*2+1,k++) {
               if (!sieve[i]) {
                       for(j = i*i; j < size; j=j+i) {sieve[j]=1; }
               }
       }
       for (i=2,j=0,k=1; i<size; i++) {

       if (!sieve[i]) { arr[j++]=i; }
       }
       free(sieve);
}
int main() {

    sieve(SIZE);

	char number[15],*file;
	int n,flag=0;
	while((file = fgets(number,sizeof(number),stdin)) !=NULL && flag!=1){
		n=atoi(number);
		if(!flag){
			flag=n;continue;}


		 printf("%d\n",arr[n-1]);
		 flag--;

	}

       return 0;
}

That means my interpretation of the challenge was wrong.But what else could it be?

[Adak]

The results of submissions are in a table here:
http://www.spoj.pl/status/start=140

You have to hunt around a bit to find your name, but it shows you submitted several times. The first few had a run-time error (sig fault), one is marked as exceeding the time limit, and the latter submissions all had a wrong answer in them, somewhere.

Did you remember to adjust the program so the first number you receive, is the number of queries to expect, and not a request for a kth prime?

Speaking of which, I'm checking the accuracy of the SoE program, and up to 1 million, it's good.

[cse.avinash]

@Diwakar : Yep I noticed in the link.

Yep its wrong Diwakar, you are mistaken in understanding question.
your mistakes:-
1)You are not generating 5000000 prime numbers. but only 3001134 prime numbers.
2)Take 1 as test case it will not take any input.
that's why its giving wrong answer.

[cse.avinash]

@Adak :

Here's the Sieve of Atkin program, but it has not been checked for accuracy thoroughly

It will be my pleasure to know that from where you have grabbed the concept of SOA.
What I have is studied is :-

1) The algorithm completely ignores any numbers divisible by two, three, or five. All numbers with an even modulo-sixty remainder are divisible by two and not prime. All numbers with modulo-sixty remainder divisible by three are also divisible by three and not prime. All numbers with modulo-sixty remainder divisible by five are divisible by five and not prime. All these remainders are ignored.

2) All numbers with modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1. These numbers are prime if and only if the number of solutions to 4x2 + y2 = n is odd and the number is squarefree.

3) All numbers with modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime if and only if the number of solutions to 3x2 + y2 = n is odd and the number is squarefree.

4) All numbers with modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only if the number of solutions to 3x2 − y2 = n is odd and the number is squarefree.

None of the potential primes are divisible by 2, 3, or 5, so they can't be divisible by their squares. This is why squarefree checks don't include 22, 32, and 52.

Your code doesn't seems to have modul0 60 division..:-/ and I didn't understand what is x and y... :(

[Adak]

@CSE: I used the pseudo code on Wikipedia, right below the description of the algorithm, as my guide in coding it. The algorithm description (which tends to be mathematical and deal with concepts), can be quite different than the implementation in code. The effect however, should be identical.

Sieve of Atkin is a fast algorithm, it's just not quite AS fast, and I did not find any faster version of it, except primegen, which is almost 80 files, and includes arrays of (I love this!) prime numbers! So 1) primegen version is WAY too big, 2) it cheats, and 3) the version that is small enough is just not faster! I've timed it 30 times, and it never was as fast as a good Sieve of Eratosthenes program.

If you can find another program, I'll be glad to test it on the same computer, so we can see how it does.

Right now, I believe you have a program that's fast enough, and it's time to move into setting it up to run in the contest, using Smeagel's idea.

I've tested the Sieve of Eratosthenes program for accuracy, and it's 100% correct for the first million primes, (which is 15,485,863). I'll finish with the rest of it, in about an hour, but I don't expect any problems with it.

The next question is how big should you make the primes array, to narrow down the gap between the primes that may have to be generated?

[cse.avinash]

With the diwakar's link, a new approach to SOE which is little faster than my approach to SOE, and within the memory bound limits..:)
here is the code:--

#include <stdio.h>
#include <stdlib.h>
#include<time.h>
int arr[5000000];
int size=86028130;
int main() {
    double start,end;
    start=clock();
           int i,j,m=0;
       char *sieve = calloc(size, 1);
       for (i=2; i*i <= size; i++) {
               if (!sieve[i]) {
                       for(j = i+i; j < size; j+=i) { sieve[j] = 1; }
               }
       }
       for (i=2; i<size; i++) {
               if (!sieve[i])  arr[m++]=i;
       }
       free(sieve);
       end=clock();
       printf("%d",m);
       printf("\n\n%f",(end-start)/CLOCKS_PER_SEC);
       return 0;
}

[Adak]

So you CAN fit all the prime numbers into memory and still pass the memory requirement for the challenge?

If so, that's great news! Crushing for Smeagel and his plan, of course, but maybe we can encourage the neighbors on his block to give him extra good Halloween candy tonight! ;) His plan was resourceful, so he gets a pat on the back for that, even if his plan is not going to be used.

Just finished testing the Sieve of Eratosthenes program for accuracy. It was perfect to all 5 million primes, so I don't expect any problems with CSE's program, in that regard either.

[cse.avinash]

So you CAN fit all the prime numbers into memory and still pass the memory requirement for the challenge?

yep..now memory issues has been resolved for that challenge but time limit is still exceeding..:(

#include <stdio.h>
#include <stdlib.h>
#include<time.h>
int arr[5000000];
int size=86028130;
int main() {
    double start,end;
    int q,k;
    start=clock();
           int i,j,m=0;
       char *sieve = calloc(size, 1);
       for (i=2; i*i <= size; i++) {
               if (!sieve[i]) {
                       for(j = i+i; j < size; j+=i) { sieve[j] = 1; }
               }
       }
       for (i=2; i<size; i++) {
               if (!sieve[i])  arr[m++]=i;
       }
       free(sieve);
         q=50000;
                 for(i=1;i<q;i++)
               printf("%d\n",arr[i-1]);
       end=clock();
       printf("%d",m);
       printf("\n\n%f",(end-start)/CLOCKS_PER_SEC);
       return 0;
}

taking 16.3s for my computer

[Adak]

I ran it twice, and it took 4.62 seconds both times, so whether you are OK on time or not, will depend on the testing system.

Sounds like you had stuff busy in the background, or your computer was just busy RUNNING AWAY FROM THE ZOMBIES!! ;)

You won't know how it does now, until you submit it and let them test it.

Good Luck!

[cse.avinash]

yep its showing time limit exceeded

[Adak]

What was the time?

[Smeagel13]

Let me get this straight, we are going down the road of storing all the primes at compile time and just reading them out at runtime? If so, i'm back in ... fresh drawing board!

[cse.avinash]

ooopss that contest uses pentium 3 processor....as i asked their..

an after restarting my system its showing 16.3s.