find the nth prime prime number - Page 3

[Adak]

His program generates the primes fast enough (I thought!) that we didn't need to save the primes directly, inside the program..

@CSE do they test on YOUR PC, or test on THEIR PC?

Well, that's another fine mess!;)

I've got to go grab some lunch and do some errands, but I'll see what we can do to optimize the program.

Right now, I think it looks possible and necessary to add some primes right into the program's array, OR add some 0's to the sieve array directly, instead of by calculating them all.

To answer your question Smeagel - I'm pondering the matter, but using a gapped table of primes, appears unnecessary. Size is now OK.

[cse.avinash]

they test on their pc's

[Adak]

Good that they do the testing - that way it's fair for everyone.

OK, to the speed up's:

Idea #1:
Write out sieve 1's and 0's to a file. Take the LAST part of that file, say 4,000 digits, and copy them into an aux1 array, in main(). Now lower the top of the for loop for calculating the sieve, by the number of digits you put into aux1[].
(and just let the system calculate how large aux1[] is)

After that loop is done, memcpy into the top of sieve, the aux1 data (see below). Since memcpy is very fast, and the looping applies to every number less than or equal to the root of size (86M+), it makes a nice speed up.

Here's an example, run it on your system, and compare it's time with the time from the previous CSE program, just above here. With just under 2k digits, I saved almost a second and a half, which is about 25% off the prior run time.

I have not checked it for accuracy, probably there's something one off, etc. But I believe the idea is sound.

Code source file size shows as 3K now (up from 1K), but those numbers are always rounded up in Explorer. We have a limit of < 10K, for the contest.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<time.h>
#define size 86028122

int arr[5000000];
//int size=86028122; //30;
//char sieve[size]= {'\0'};
int main() {
   double start,end;
   int q;  //delete k
   char aux1[]={"111111111111111111111111111111111111111110111111111011111111111111111111111111111110111011111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111011111111111111111111111011111011111110111110111110111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111110111111111111111011111111111111111111111011111011111111111110111111111111111111111110111111111011111111111110111111111111111110111111111111111110111111111010111111111011111111111111111011111111111110111111111110111111111111111110111110111111111111111111111110111111111011111111111011111011111110111111111111111111111111111111111011111111111111111111111110111111111111111011111111111111111010111110111111111110111111111111111111111011111111111110111111111111111111111110111111111011111111111111111011111111111110111111111011111111111111111111111111111011111111111111111110111111111111111011111111111111111111111111111110111111111111111111111111111111111111111011111111111111111111111110111111111110111011111111111111111111111111111011111111111111111111111111111011111111111111111111111010111011111111111110111110111111111111111110111111111110111111111111111110111111111111111111111011111110111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111011111111111111111111111111111010111111111111111111111111111110111111111110111011111111111111111111111111111111111111111111111111111111111011111111111111111110111011111111111111111011111110111110111111111111111111111111111111111110111111111111111111111111111111111011111111111111111111111111111111111011111110111111111111111111111111111111111110111011111111111111111111111111111011111111111111111111111111111111111111111111111110111111111111111111111110111111111110111011111111111011111111111011111111111111111111111110111111111110111011111111111111111111111111111111111111111110111011111111111011111110"};
   //FILE *out;
   //out=fopen("aux1.txt", "w");

   //printf("%c%c\n", sieve[0], sieve[1]);
   //getchar();
   //return 0;

   start=clock();
   int i,j,m=0;
   char *sieve = calloc(size, 1);
   m=size-1956; //I took in 1956 digits for aux1[]
   for (i=2; i*i <= m; i++) {  //was i<=size
       if (!sieve[i]) {
           for(j = i+i; j < size; j+=i) { sieve[j] = 1; }
       }
   }
   //printf("%d", strlen(aux1));  //I believe! ;)
   memcpy(sieve+m,aux1,1956);
   putchar('!');        //success so far!
   for (i=2,m=0; i<size; i++) {
       if (!sieve[i])  arr[m++]=i;
       //fprintf(out, "%d", sieve[i]); //gave me raw data for aux1[]
   }
   
   //fclose(out);  //file for raw data going to aux1[]
   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;
}

Let me know what you think and how it tests for you.

[Adak]

Looking at the code for the challenge so far, I don't see much else that can be optimized, unless we print directly to the video memory. That is something I haven't done in a decade, at least.

So I believe this is where the speed up's will be found - in creating the prime numbers. It's already fast, but we have to go to extremes to meet this challenge.

I'm try it with 5,000 char's next (same as above, but with more chars in the aux1[] array). Then I'll ensure it's accurate if it looks promising, which I believe it will.

If you have more idea's on optimizing this, by all means post up, and give it a try.

Ya know, using some magic pixie dust on the program, would be a whole lot easier! ;)

This may not be accurate yet, but it will work.

[Adak]

My IDE (editor) went bonkers on me when I tried to use 5,000 chars - I mean it refuses to print the 1's and 0's that I have pasted into the array!

Trick or Treat!

So the next try is to put in the N highest primes, directly into the prime numbers array. Hopefully, the IDE editor will handle separate numbers better than it handles long strings of digits as chars.

[Adak]

The numbers are working out OK, so far. CSE, your program looks a lot different, but you'll still recognize it -- I'm giving it it's own drivers license. ;)

I'm trying two idea's:
1) having a big[] array with the top prime numbers, and
2) having a tiny[] array with the smallest prime numbers.

Together, they decrease the time needed to produce all the primes for the arr[] array of all the primes. Not by much, but it all helps, and adds up, of course.

After adding this stuff, I'm putting it back together again.

I'll post again when I have something for ya. ;)

[cse.avinash]

yep a good idea..that i was taking about to make a segment of array to be displayed.
16.5 sec is reduced to 13.4 sec.

m=size-1956;

what is 1956 ? why this number is chosen for the size of aux1[].?
didn't understand...:-/

[Adak]

I wanted to get about 2K char's, and that's what I wound up with. ;)

Right now I'm trying an approach using numbers, instead of sieve char's. Both are able to speed up the program in tests so far. The numbers are easier to work with, and check for accuracy with the program, but the char's allow more items to be used, since they're smaller.

I'll be touching up the numbers version today. Late today or tomorrow, I'll post it up so you can try it. I had to remove a lot of the numbers unfortunately, because the program was too big (over 10KB).

After that, I'm going to work again on the sieve data char's, and see what can be done to improve that version, some more. My C editor does NOT like a lot of char's though - not sure why. Maybe I'm pasting in too many chars at one time? Don't know. PITA though when it corrupts the program so the file can't be saved or compiled, either one. <mad!>

If you are looking for a new hobby that takes a lot of time, I can recommend trying to optimize programs that are already fast. ;)

[Adak]

I haven't check this for accuracy, but CSE, Smeagel and Diwakar, give this version a try, and compare it with the version just above here, using char's. Which is better, and by how much?

I know I can get a bit more optimizing done to the char version. This number version, is about as optimized as I know how, right now. For the size limit, it just will fit in at under 10KB (with a bit of unsightly stuffing).

I wouldn't bother submitting it because I don't believe it's accurate yet, but that is the easy part, I've found.

Do you submit executable programs, or source code and they compile it, for the tests?

Let me know how it does.

#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<time.h>
#define Size 86028122
#define BigQty 1011
unsigned int arr[5000001];
int main() {double start,end; unsigned int big[BigQty]={ 
86009723,86009731,86009741,86009743,86009773,86009797,86009801,86009813,86009863,86009873,
86009909,86009947,86009983,86010007,86010011,86010013,86010031,86010059,86010077,86010083,
86010091,86010103,86010109,86010139,86010167,86010203,86010217,86010229,86010233,86010241,
86010263,86010299,86010347,86010349,86010367,86010371,86010383,86010391,86010479,86010541,
86010557,86010569,86010577,86010581,86010601,86010637,86010649,86010689,86010719,86010737,
86010751,86010761,86010763,86010767,86010779,86010787,86010809,86010817,86010851,86010857,
86010887,86010901,86010941,86010949,86010971,86011001,86011021,86011027,86011031,86011061,
86011067,86011069,86011073,86011087,86011139,86011147,86011151,86011169,86011181,86011229,
86011231,86011243,86011249,86011253,86011259,86011307,86011327,86011333,86011337,86011357,
86011379,86011411,86011417,86011441,86011463,86011493,86011501,86011507,86011511,86011529,
86011543,86011561,86011603,86011609,86011637,86011649,86011657,86011663,86011669,86011703,
86011711,86011753,86011759,86011777,86011781,86011811,86011831,86011867,86011873,86011957,
86011963,86011969,86012033,86012041,86012051,86012063,86012077,86012081,86012093,86012099,
86012117,86012123,86012141,86012189,86012191,86012233,86012243,86012263,86012273,86012281,
86012287,86012327,86012357,86012369,86012371,86012393,86012413,86012431,86012441,86012471,
86012489,86012539,86012551,86012557,86012567,86012603,86012609,86012627,86012653,86012669,
86012683,86012687,86012743,86012747,86012749,86012777,86012779,86012807,86012819,86012821,
86012833,86012837,86012851,86012863,86012873,86012887,86012903,86012917,86012923,86012933,
86012947,86012951,86012963,86012977,86012999,86013023,86013041,86013089,86013097,86013113,
86013119,86013131,86013139,86013157,86013181,86013229,86013253,86013281,86013283,86013289,
86013293,86013299,86013311,86013359,86013397,86013407,86013409,86013439,86013443,86013457,
86013469,86013497,86013509,86013511,86013533,86013569,86013593,86013601,86013649,86013661,
86013667,86013673,86013701,86013743,86013749,86013751,86013773,86013787,86013791,86013793,
86013827,86013847,86013853,86013869,86013881,86013899,86013911,86013919,86013953,86014009,
86014031,86014037,86014039,86014063,86014069,86014073,86014079,86014091,86014129,86014133,
86014141,86014163,86014193,86014231,86014241,86014249,86014259,86014267,86014289,86014301,
86014343,86014363,86014391,86014403,86014483,86014499,86014517,86014561,86014567,86014573,
86014589,86014619,86014627,86014637,86014651,86014661,86014681,86014693,86014699,86014703,
86014711,86014723,86014727,86014741,86014757,86014769,86014777,86014793,86014823,86014837,
86014879,86014909,86014913,86014967,86014969,86014997,86015011,86015021,86015023,86015057,
86015077,86015099,86015113,86015117,86015143,86015159,86015177,86015183,86015191,86015219,
86015227,86015231,86015233,86015287,86015309,86015317,86015327,86015341,86015357,86015387,
86015411,86015431,86015453,86015459,86015477,86015507,86015509,86015557,86015591,86015647,
86015651,86015659,86015689,86015701,86015707,86015723,86015771,86015777,86015789,86015803,
86015807,86015819,86015833,86015879,86015893,86015921,86015927,86015987,86016013,86016019,
86016031,86016043,86016053,86016071,86016079,86016109,86016131,86016143,86016163,86016179,
86016193,86016197,86016199,86016223,86016239,86016257,86016269,86016313,86016317,86016341,
86016361,86016373,86016421,86016443,86016457,86016467,86016473,86016479,86016487,86016547,
86016559,86016563,86016577,86016611,86016613,86016653,86016673,86016737,86016761,86016767,
86016779,86016793,86016841,86016863,86016901,86016907,86016911,86016913,86016919,86016937,
86016943,86016977,86017007,86017013,86017021,86017027,86017049,86017073,86017091,86017111,
86017147,86017163,86017181,86017187,86017207,86017249,86017271,86017291,86017397,86017411,
86017417,86017441,86017453,86017511,86017513,86017523,86017543,86017553,86017573,86017577,
86017583,86017601,86017609,86017619,86017627,86017651,86017691,86017697,86017709,86017717,
86017727,86017733,86017783,86017801,86017817,86017823,86017829,86017837,86017843,86017847,
86017873,86017879,86017891,86017927,86017979,86018021,86018027,86018029,86018057,86018059,
86018063,86018069,86018071,86018077,86018083,86018161,86018167,86018171,86018201,86018203,
86018213,86018221,86018237,86018371,86018389,86018407,86018423,86018441,86018467,86018473,
86018483,86018501,86018503,86018531,86018539,86018563,86018579,86018593,86018617,86018641,
86018659,86018677,86018683,86018693,86018711,86018717,86018761,86018773,86018797,86018813,
86018819,86018839,86018857,86018869,86018903,86018917,86018941,86018953,86018981,86018993,
86019001,86019007,86019013,86019019,86019047,86019067,86019083,86019121,86019139,86019161,
86019163,86019169,86019187,86019209,86019247,86019253,86019257,86019277,86019281,86019313,
86019341,86019343,86019359,86019419,86019449,86019469,86019509,86019511,86019533,86019551,
86019569,86019589,86019601,86019613,86019617,86019629,86019641,86019649,86019671,86019679,
86019683,86019691,86019721,86019727,86019751,86019757,86019811,86019833,86019851,86019877,
86019883,86019911,86019937,86019961,86019991,86020031,86020063,86020073,86020093,86020111,
86020117,86020127,86020139,86020147,86020157,86020159,86020183,86020211,86020217,86020223,
86020229,86020237,86020241,86020267,86020283,86020303,86020327,86020379,86020393,86020399,
86020421,86020427,86020439,86020463,86020469,86020477,86020507,86020513,86020559,86020577,
86020603,86020607,86020609,86020633,86020687,86020709,86020717,86020721,86020789,86020807,
86020811,86020813,86020817,86020849,86020871,86020981,86021011,86021017,86021021,86021051,
86021053,86021057,86021059,86021077,86021101,86021107,86021141,86021153,86021161,86021167,
86021179,86021261,86021329,86021359,86021381,86021389,86021393,86021431,86021459,86021483,
86021489,86021527,86021539,86021561,86021623,86021653,86021657,86021659,86021669,86021693,
86021699,86021711,86021729,86021737,86021753,86021821,86021827,86021833,86021839,86021843,
86021849,86021857,86021893,86021939,86021951,86021953,86021963,86021983,86022011,86022019,
86022029,86022043,86022049,86022121,86022143,86022161,86022169,86022191,86022197,86022203,
86022221,86022229,86022257,86022259,86022263,86022281,86022301,86022371,86022401,86022421,
86022449,86022451,86022457,86022463,86022467,86022479,86022511,86022529,86022539,86022571,
86022577,86022589,86022593,86022619,86022623,86022631,86022637,86022641,86022653,86022659,
86022667,86022721,86022733,86022751,86022773,86022803,86022809,86022821,86022847,86022851,
86022857,86022877,86022883,86022913,86022917,86022929,86022953,86022973,86022983,86023001,
86023027,86023037,86023057,86023073,86023079,86023097,86023099,86023117,86023139,86023141,
86023169,86023183,86023219,86023229,86023253,86023271,86023277,86023291,86023303,86023307,
86023319,86023361,86023391,86023403,86023411,86023439,86023459,86023463,86023471,86023477,
86023493,86023501,86023517,86023579,86023589,86023591,86023601,86023627,86023649,86023669,
86023673,86023681,86023687,86023709,86023741,86023747,86023753,86023759,86023787,86023879,
86023891,86023897,86023907,86023909,86023937,86023957,86023967,86024009,86024017,86024069,
86024087,86024137,86024143,86024161,86024171,86024203,86024207,86024219,86024231,86024243,
86024249,86024251,86024269,86024291,86024293,86024303,86024321,86024327,86024363,86024377,
86024399,86024417,86024447,86024453,86024461,86024479,86024483,86024503,86024513,86024567,
86024611,86024621,86024633,86024651,86024677,86024699,86024707,86024713,86024749,86024767,
86024789,86024791,86024801,86024821,86024857,86024863,86024867,86024881,86024893,86024909,
86024921,86024923,86024927,86024941,86024957,86024959,86024971,86024977,86024987,86025007,
86025013,86025019,86025053,86025061,86025077,86025131,86025133,86025143,86025157,86025193,
86025197,86025209,86025263,86025319,86025347,86025349,86025371,86025377,86025439,86025449,
86025469,86025479,86025487,86025523,86025529,86025553,86025587,86025601,86025619,86025623,
86025631,86025647,86025649,86025683,86025691,86025701,86025739,86025761,86025769,86025781,
86025791,86025809,86025829,86025847,86025853,86025869,86025871,86025881,86025889,86025893,
86025937,86025959,86025971,86025991,86026051,86026063,86026067,86026133,86026207,86026217,
86026249,86026253,86026301,86026349,86026373,86026379,86026387,86026393,86026399,86026439,
86026513,86026529,86026553,86026559,86026573,86026597,86026607,86026621,86026639,86026657,
86026667,86026669,86026679,86026697,86026711,86026723,86026741,86026747,86026771,86026781,
86026793,86026799,86026807,86026841,86026867,86026883,86026901,86026903,86026909,86026921,
86026943,86026957,86026981,86026991,86027009,86027023,86027033,86027063,86027083,86027099,
86027131,86027171,86027197,86027209,86027213,86027243,86027273,86027297,86027299,86027303,
86027317,86027323,86027341,86027353,86027371,86027393,86027401,86027419,86027509,86027519,
86027549,86027551,86027581,86027593,86027597,86027657,86027677,86027681,86027699,86027707,
86027713,86027749,86027783,86027819,86027827,86027863,86027867,86027897,86027947,86027971,
86027983,86027987,86027999,86028011,86028037,86028049,86028053,86028097,86028101,86028113,
86028121 }; start=clock(); unsigned int i,j,small=Size-BigQty; char *sieve = calloc(small,1);  

for (i=2; i*i <= small; i++) 
   {if (!sieve[i]) 
      {for(j = i+i; j < Size; j+=i) { sieve[j] = 1; }}}

small=big[0]; 

for (i=0,j=0; i<small; i++) 
   {if (!sieve[i])  
      arr[j++]=i;} 

small=5000001-BigQty;
for(i=0;i<BigQty;i++) 
   arr[small++] = big[i]; 

free(sieve); 
for(i=2475000;i<2525000;i++) { //centered around mid range 2,500,00
printf("%d\n",arr[i]);} end=clock(); printf("\n\n%f\n",(end-start)/CLOCKS_PER_SEC); return 0;}

[cse.avinash]

@Adak :- What time is giving this program in your system. You have applied your brain, but doesn't seems to affect much. Showing 15.6s.

I have told I tried this approach with 5000000 prime numbers but after output redirection to file that file doesn't open showing not responding.

Its very strange to me the program which takes 13.5s to compile in windows takes 3.4s in in linux, is linux doesn't run much processes as compared to windows .?:-/

[Adak]

It runs in just under five seconds on my system. The char version above does about the same, but I can optimize it still more.

If you want to save data to a file, add an end of file char to the stream at the end: ctrl+z on Windows and DOS, and ctrl+d on Linux (not sure for linux though). fclose(filePointerName), should do that for you, on your system.

Linux has a lot of processes, but the question is, how much cpu time are they taking (how active are they)? Some versions of Linux are pretty active - others are very responsive.

Just for an idea for you, the time on my system, breaks down to:

0.95 seconds to get all the prime numbers found, and loaded
3.82 seconds to print the 50,000 primes in the mid range of the contest (2,475,000 to 2,525,000).

I'm trying to reduce the 0.95 seconds part, and that's quite difficult, because there isn't much THERE to start with.

I've looked into printing the primes faster, but I'm unsure how to do that - especially when it's a strangers computer you know nothing about.

The easiest way may be to just reset his computer clock while the program is running. Put it back about 2 seconds or so! ;)

I have some other idea's, but I have a bug in the character based program that I have to fix first. Then I'll get to work on some other ideas to cut down the time. Those involve:

1) The logic we use in creating the sieve array data, and

2) The way the aux1 array is stored.

Both can be improved, imo.

[Adak]

This is the big idea for an improvement:

In this code

for (i=2; i*i <= Size; i++) {  
      if (sieve[i]==0) {
           for(j = i+i; j < Size; j+=i) { sieve[j] = 1; } 
       }
   }

i is simply incremented. So after testing for 2, and 3, i will be testing for 4 and 6, and 8, and 10, etc.

Next version will eliminate that redundancy and definitely speed up this portion of the program.

[cse.avinash]

One more thing I want to add in the problem which I forgot is that You can't exceed 10000 characters in a program i.e., source limit is 10000 bytes

[Adak]

Forget my last post - you can do that with trial by division for a nice speed up, but it doesn't work with Sieves.

I've got it down now to 3.56 seconds (including printing 50K primes), but it's too long to be accepted. I'll shorten it, clean it up, and post it after I get it checked for accuracy.

I went with the numbers version, but streamlined how it works.

CSE, do you submit code or is it an executable file that gets tested?

I can't begin to tell you how many times I crashed this program, while working with it. Amazing how well the newer operating systems handle it.

[D33wakar]

CSE, do you submit code or is it an executable file that gets tested?

No,you just have to submit your code.
I compiled and ran your both programs and it took about 16 seconds for the version with direct numbers and about 13 seconds for the version with char array( intel core 2 duo, 2.22 GHz).The chars version was not accepted by my ide, so I had to build it in the command line.
Then I submitted the program I was working on( after editing a little bit),

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

#define SIZE 86028122
int arr[5000000]={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; i<size; i++) {
           if (!sieve[i]) { arr[j++]=i; }
       }


       free(sieve);
}
int main(void) {
	
    sieve(SIZE);

	char number[15],*file=NULL;
	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;
}

I submitted it because, it was taking about 4.79 seconds on my PC and only 2.26 seconds on ideone which the site recommends to test your code.But it shows time limit exceeded whenever I submit it to the site itself.Frustrating, isn't it?

2)Take 1 as test case it will not take any input.
that's why its giving wrong answer.

But I was reading the input from a file, otherwise how else would you give this kind of input:

8
1
10
100
1000
10000
100000
1000000

[cse.avinash]

.Frustrating, isn't it?

Yep its really very frustrating.
I checked , 3 users have got accepted this question and I am wondering how any one can get accept this problem in just 0.64s..:-/
@Adak, @Diwakar @smeagle
I thaught a plan , can parallel processing of numbers to be found and stored in different arrays be possible ?
I want to say let there be five different arrays say arr1[1000000], arr2[1000000],
arr3[1000000],arr4[1000000],arr5[1000000] for 5000000 prime numbers and there will be pipelining in storing prime numbers in all arrays, can this be possible, if it is , I don't know how to do it..?

[Adak]

It's all possible, but not with the size limit they have. Good thinking, though! ;)

Plus, you don't know if the PC it's being judged on, will allow the program to use multiple cores or not. 0.64 seconds and such, seems like the program would have to load the primes up into an section of memory on the testing PC, then have stdin processed, and instantly directed to the right answer, via pointers. I could be wrong, but I can't print out 50,000 prime numbers that fast!

Don't sweat it, we're just getting to the heart of the matter. ;)

[cse.avinash]

I asked there in the forum, they told me to solve this question first before solving that question, there is a lots of concept here in this question to solve that question..

[Adak]

If your time limit is exceeded, you aren't told by how much correct?

I see a *possible* part that could be improved, in Diwakar's code. I'll have to check on that before I know for sure though.

That second problem is this problem "light", in my opinion. I like this one! It's got some heft to it. ;)

[Adak]

I changed a small part of your code here, Diwakar. It's now a bit faster.

int main(void) {
	
   sieve(SIZE);
	//char number[15],*file=NULL;
   unsigned int n,flag=0,query;
   fscanf(stdin, "%d", &query);
   while((fscanf(stdin, "%u", &n)) > 0)
      printf("%u\n",arr[n-1]);

   
   return 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--;
      }
   */
}

I made no changes to any other function beside main(), except to make all int's into unsigned int's, instead of int's. The improvement was using fscanf(), instead of fgets and atoi.

[Smeagel13]

What's going on here?!!! http://www.spoj.pl/ranks/PRIME1/

The top time is 0.00 closely followed by times of 0.01 ...

[Adak]

Three ideas come to mind:

1) There are quick tests to find "probable" primes. If you used two of these tests, you could get a very high percentage of the primes correct. If you used enough of them to find ALL the correct primes however, it takes longer than using other algorithms.

2) Someone has learned how to hack the test rig, resetting it's clock so it matches, or almost matches, the time the test began, or telling it to pass this test, instantly.

3) If you could create a "virtual console" in memory, and send your answers there, and have the answers checked by the test rig, from there, then you would remove a large bottleneck. Printing out the data is the biggest bottleneck to our problem, by far. Moving it up to RAM speed would be a big time saver.

0.0 seconds though? No, not legit.

[jwenting]

Skip all even numbers. That will cut your loop in half: for(i=3;i<=root;i+=2)

And skip any number higher than the square root of the number being tested as well.
Can't remember what the proof of that is, but it works :)

Of course for small values of n, calculating n/y for all y<n might be faster than calculating sqrt(n).

[Adak]

@Jwenting:

We are skipping every even number and we stop at the root as well, although we don't always use the sqrt() function.

Well guys, I hate to say it but:

"I found the answer!"

It was staring me right in the face, from day 1 of this thread. Yeah, it's embarrassing, and you will be embarrassed as well, when I tell you."

I'm tweaking it around a bit right now, but it's cut the time in half, already.

Let the anticipation begin!!

[Smeagel13]

@Jwenting:

We are skipping every even number and we stop at the root as well, although we don't always use the sqrt() function.

Well guys, I hate to say it but:

"I found the answer!"

It was staring me right in the face, from day 1 of this thread. Yeah, it's embarrassing, and you will be embarrassed as well, when I tell you."

I'm tweaking it around a bit right now, but it's cut the time in half, already.

Let the anticipation begin!!

Come on man!!! I can't wait!

[Adak]

We've noted several times that the bottleneck for the program, is printing. Every system will be different, but on my system the printing part takes 4 X's as long, as the calculation of the primes part of the program.

And look at how many times we call printf: 50,000 times.

Every call to printf() incurs a small expense, because printf() can decode a boatload of formats, etc. So use those format features, and call printf() a LOT less. How about 125 X less? ;)

125 is good because it is a factor of 50,000, and it closely matches a multiple of two and 8 (128), which is an eight of a Megabyte. Computers tend to be most efficient at those multiples of 2 and 8 sizes.

This was the print statement that knocked about 30% off my previous best time:

printf("%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n"
   "%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n"
   "%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n"
   "%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n"
   "%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n"
   "%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n%u\n",
   p[i],   p[i+1], p[i+2], p[i+3], p[i+4], p[i+5], p[i+6], p[i+7], p[i+8], p[i+9], p[i+10],p[i+11],
   p[i+12],p[i+13],p[i+14],p[i+15],p[i+16],p[i+17],p[i+18],p[i+19],p[i+20],p[i+21],p[i+22],p[i+23],
   p[i+24],p[i+25],p[i+26],p[i+27],p[i+28],p[i+29],p[i+30],p[i+31],p[i+32],p[i+33],p[i+34],p[i+35],
   p[i+36],p[i+37],p[i+38],p[i+39],p[i+40],p[i+41],p[i+42],p[i+43],p[i+44],p[i+45],p[i+46],p[i+47],
   p[i+48],p[i+49],p[i+50],p[i+51],p[i+52],p[i+53],p[i+54],p[i+55],p[i+56],p[i+57],p[i+58],p[i+59],
   p[i+60],p[i+61],p[i+62],p[i+63],
   p[i+64],p[i+65],p[i+66],p[i+67],p[i+68],p[i+69],p[i+70],p[i+71],p[i+72],p[i+73],p[i+74],p[i+75],
   p[i+76],p[i+77],p[i+78],p[i+79],p[i+80],p[i+81],p[i+82],p[i+83],p[i+84],p[i+85],p[i+86],p[i+87],
   p[i+88],p[i+89],p[i+90],p[i+91],p[i+92],p[i+93],p[i+94],p[i+95],p[i+96],p[i+97],p[i+98],p[i+99],
   p[i+100],p[i+101],p[i+102],p[i+103],p[i+104],p[i+105],p[i+106],p[i+107],p[i+108],p[i+109],p[i+110],
   p[i+111],p[i+112],p[i+113],p[i+114],p[i+115],p[i+116],p[i+117],p[i+118],p[i+119],p[i+120],p[i+121],
   p[i+122],p[i+123],p[i+124]); }

Note that i+124 numbers is 125 numbers being printed out. You may need to lower your i<5000000 part of our printf() statement, by one (I had to, but I used a slightly different index system than most).

I initially had 45% improvement with much more than 125 numbers being printed per call to printf, and using a much larger aux1[] size, but I had to cut them both down in size, to make the program under 10KB.

Second topic:

Just an idea, completely untested.

What if we took in ALL the queries from the tester, into an array, and quickly sorted them (time: maybe 0.2-1.0 seconds). Then we start the prime finding loop, and as soon as we find one, (in Sieve loop), that matches the next request, we print it solo, just that one number and newline.***

Now look at what's changed:

* We don't need to generate all the primes, we only will generate until the highest prime number that is requested.

* No primes[] array is not needed anymore. We get the answer right from the sieve loop.

* The printing might not be such a bottleneck, since there are gaps between the queries, so the sieve loop could work on (although it would be slowed down).

*** perhaps a faster idea would be as above, but keep the printing outside the sieve loop. Print with a big number per print call, (an obvious speed up), only after the sieve loop has found all the prime numbers for us.

Maybe print out 512 numbers with each call to printf()?

We keep the primes loop, and fill it like now, but we fill it ONLY with the matching numbers from the queries. We don't need a primes array of 5 million anymore. Just 50,000 primes stored would be fine, because we'd have the right 50,000 primes.;)

Summing up, I believe the new printing idea will allow your programs to beat the test, if it's otherwise well designed, and accurate.

I am now running my test program version with this printing format string, and getting times of 2.62 seconds. That's about 1 1/2 seconds faster than before. Try it on your programs and see how it works for you.

@Diwakar, I inserted part of your sieve loop (the nested for loop at the bottom of it), and found I wasn't getting all the prime numbers - lots of them, but not all. You may want to check it (but it could be just the interaction between my loop logic, and yours, in the top half of the larger loop).

[Adak]

I'm putting together a version of the primes test program, using the sorting approach mentioned in the previous post. Run this program on your system, and see what times you get - I'm getting 0.000 seconds (no measurable time). Quicksort does me proud on randomized numbers! <3 Quicksort!

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

void quickSort(unsigned *, unsigned, unsigned);

int main(void) {
unsigned int k,maxq=0,queNum=50000, *que;
   clock_t start,stop;  start=clock();    
   //input for the test
   //fscanf(stdin, "%u",&queNum);
   que = malloc(queNum * sizeof(unsigned int));
   //for(i=0;i<queNum;i++) {fscanf(stdin,"%u",&que[i]); if(que[i] > maxq) maxq=que[i];}
   for(i=0;i<queNum;i++) {que[i] = rand() % 50000+1; if(que[i] > maxq) maxq=que[i];}
   printf("maxq: %u",maxq); //getchar();

   //sort que
   start=clock();
   quickSort(que, 0, queNum-1);
   //Check results >> for(i=0;i<queNum;i++) {printf("i: %u  que[i]: %u\n",i, que[i]); if(i % 20 == 0) getchar();}
   stop = clock() - start; printf("\n\nTime was %f seconds\n", (double) stop/CLOCKS_PER_SEC); 

   getchar();
   return 0;
 }
}
void quickSort(unsigned *a, unsigned lo, unsigned hi) {
   unsigned i, j, pivot,temp;
   if(lo == hi) return; 
   i=lo; 
   j=hi;
   pivot= a[(lo+hi)/2]; 

   /* Split the array into two parts */
   do {    
      while (a[i] < pivot) i++; 
      while (a[j] > pivot) j--;
      if (i<=j) { //without the = in there, it's an endless loop
         temp= a[i];
         a[i]= a[j];
         a[j]=temp;
         i++;
         j--;
      }
   }while (i<=j);
    
   if (lo < j) quickSort(a, lo, j);
   if (i < hi) quickSort(a, i, hi);
}

Two things of note:

1) I have a much shorter version of Quicksort - called Quickshort - if size is critical for your program (it's only 4 or 5 lines). This version is the speed demon, however.

2) The "hi" parameter to this version of Quicksort is the highest VALID index you want sorted - NOT the size of the array. (for array[500], you send it to quicksort with a hi of 500-1, not 500.).

I'll report back as soon as I get some testing done on the program, using this sorting idea, within the whole program.

Funny of the Day: Run your program for time, with the console window at it's full size. Note the time. Now shrink the window down to a tiny little 2 rows of text showing, and run it again. <crack up>

[Adak]

Well, well, well, dept:

Just learned that my Quicksort version does NOT work with unsigned int's in my compiler - use signed (regular) integers. I haven't tried long's or long long's yet.

[D33wakar]

Every call to printf() incurs a small expense, because printf() can decode a boatload of formats, etc.

Yeah,I couldn't agree with you more.

Second topic:

Just an idea, completely untested.

What if we took in ALL the queries from the tester, into an array, and quickly sorted them (time: maybe 0.2-1.0 seconds). Then we start the prime finding loop, and as soon as we find one, (in Sieve loop), that matches the next request, we print it solo, just that one number and newline.***

Now we're talking! That's a brilliant idea. I wondered, why would you need the number of queries in the input at first, since you're given all the numbers for which you have to find the primes for.Now I know, you're supposed to use that in your code, it's like a hint right?

Maybe print out 512 numbers with each call to printf()?

Hmm, interesting!

@Diwakar, I inserted part of your sieve loop (the nested for loop at the bottom of it), and found I wasn't getting all the prime numbers - lots of them, but not all. You may want to check it (but it could be just the interaction between my loop logic, and yours, in the top half of the larger loop).

It may be possible since i haven't tested it for all five million! But until now it has been giving correct answers.I'll check that and inform you later.
By the way, your quicksort looks fast, I'll give that a try too.

[Adak]

It IS fast! (Although it can be optimized to be about 15% faster, but then the code gets longer). Notice that the pivot is never moved? This ain't your grandma's Quicksort! I haven't found a faster and clearer example for Quicksort.

Your code snippet was giving me about 4.8 Million primes, out of the 5 Million. It wasn't clear why that was happening.

I got seriously sidetracked yesterday when I found out my favorite Quicksort was not working - I had never tried it with unsigned int's before. Had no idea unsigned int's would cause it to go off the rails. Took me a WHILE to nail that one down.

I'll have some timing data for my implementation of idea #2, later today. Should be interesting.