Posts by Adak

CAUTION: I found out the gcc C compiler does NOT like the increment of i in the printf() statment. So this:

printf("%d\n%d\n",primes[[B]++i[/B]], primes[[B]++i[/B]])

exprression, should be avoided.

I'm trying out the rather tired primes[i+1],primes[i+2],primes[i+3]
expression in a printf() statement, to see how that works.

It worked fine for me on Pelles C, but they're testing on the gcc compiler, and testing the programs, by running them on a battery powered abacus, I swear! ;)

Yes, I submitted a B(2) algorithm program for testing - "time limit exceeded". It had run in 2.6 seconds, repeatedly. Now it can't run in under 10 seconds??

C'mon! Hamster running low on food? Timex Sinclair PC getting overheated?? Grrr!

Describe your array, and which way you want to "flip" it - Rotate it 90° clockwise or counter-clockwise, or along a particular axis (specify which one). A 3 X 3 example of the array before and after the flip, would be great.

Use code tags around the example, or it will be mangled by the forum software.

This is the best "B" Algorithm speed that I can manage right now. It takes 2.6 seconds on my PC, and a lot of that speed up is due to the very large printf() calls - each one is printing out 500 numbers at a time.

I'm going to go back to the "A" Algorithm now, and see if I can tweak a bit more, using what I've learned from working on the B algorithm programs.

This is a test in the command window, with an external timer (ptime.exe), with data being redirected using stdin.

@Smeagel, you've been quiet lately, any status report?

I have never understood the desire to swap out the pivot/key in Quicksort. It's not necessary.

Your version has no if statement before the recursive calls, to allow it to always choose the smaller sub array. With a recalcitrant data set, you might run out of stack space.

This is the version of Quicksort I like. Two caveats:

1) The index data type has to be a regular (signed) type of int, with unsigned int's it fails when the index briefly goes to a -1 value.

2) The hi that is originally passed to it must be the last valid index. If you pass in an array of 100 numbers, then the last valid index is 99, and you call Quicksort with 0, and 99, not 0 and 100.

If you time it, you'll see it's faster than most other versions of (non-optimized) Quicksort.

void quickSort(int *a, int lo, int hi) {
   int 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);
}

I am not clearly getting you adak what you are trying to do with the sorting approach, but your quickshort is really fast,

Please look on to the Segmented seive algo it will make task approachable and make seive algo much more fast.
For accessing element there is nothing much problem, problem is in making seive algo fast..
so, divide and run the sieve algorithm into segments.
means first 100000, then next 100000
so on for a range only,
I am thinking and trying this.
please any one of you look into it.(Adak, smeagle, Diwakar)

That isn't Quickshort - Quickshort is only about 6 lines of code, in the whole thing! (But it's not this fast). This is a full Quicksort, and it is fast, BUT you can't use an unsigned int for any index. It has to be a regular int.

Anyway, yes! The sorting idea is out the window for this program ==> Forget it, it's Toast! ;)

I did look into both Segmented Sieve of Eratosthenes, and also Wheeled versions. The problem is, they were no faster in the tests I ran against an optimized Sieve of Era., without the segments or wheel aspects to them.

I didn't have time to look at several different examples of each, so there may be faster Segmented or Wheeled versions of the Sieve of Era. out there. I was more interested in getting a good basic version that was easy to …

The testing info on the B algorithm, second version is: 3.12 seconds in the terminal. This is the version intended to have the "B" algorithm, but it didn't quite work that way! ;)

Since the sorting idea went sour (a great idea, but it gave the results out of their original order, which I'm sure is what the test challenge requires), there was no way to directly get the data, organized as efficiently as I'd have liked. You either had to transfer the data (an extra step I did not want to have to make), or print through an index (which is just a touch slower and it adds up). I chose the latter.

Still using the very large printf() call (now at 250 numbers being printed per one call to printf() ).

Size of the file is 6.8 KB now, including some few comments that could be removed, and the few lines of code to communicate with the testing PC, that I have added.

So size is no problem.

So the overall champ -- and still king of the Challenge, is the A algorithm, with the smaller aux1 array, and using huge print calls. It's also a pain to get just right. Overall, I prefer the B algorithm. It's much easier to get working right.

A few timing facts, for the curious. These were all run on the same PC, which was otherwise not busy.

The "A" algorithm, was the one that used the Sieve of Eratosthenes, but not the best one from CSE (it was getting 4.65 on the IDE and 4.0 on the terminal). It was "almost as good as CSE's version", but it was much simpler to test with.

Note: A "terminal" is sometimes called a Command Window, in Windows.

This included an aux1 (auxiliary) array (sometimes called Big[]), that held LOTS of prime numbers (a few hundred to a few thousand), to try and get a feel for the effect on the timing. Data shows the aux1 array was helpful, but not very much. At the largest number of primes we could use for the challenge, it could save 0.3 seconds, only (on my system).

The "B1" algorithm used no aux1 or big array of primes, at all. The k queries were sorted by Quicksort, and printed as they were generated, inside the loop that finds the primes - one number per call to printf().

The "B2" version of the algorithm is similar to the B1 version except the answers are not printed right away. They're stored in an array, and then printed out with multiple numbers being printed, in a single call to printf(). I'm experimenting with printing 125 numbers per call to printf(). Also, the query (kth) numbers are not sorted.

I believe …

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.

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.

I'm always skeptical when I read code that has an index or pointer that runs out of the array bounds. The standard says you MAY be sure that it's OK, but only for 1 element AND you are never to work with the value at that address.

Code with no supporting tests, are another thing I'm cautious about. If you say that a program you post is good at something, I expect at least a little data from your testing, to support that conclusion.

There's a good deal of "hand waving and hot air" regarding programs, and I've read some great examples of it, by notable professors even. In the latest scam, the professor claimed a VERY fast prime number generator -and it was BLAZING fast. Only later did you learn it was so fast, partly because it HAD A LIST OF PRIME NUMBERS, EMBEDDED IN THE CODE! Oh for crying out loud!!

Another common example is someone claiming that their new sorting algorithm is "Faster than Quicksort". Sure, because Quicksort is an old algorithm, and the early versions weren't well studied yet. So you can easily beat the Quicksort versions from 20 years ago, but that's *NOT* beating a modern version of Quicksort!

Well, they get their names in the scholarly publications, and their tenure is quite secure, etc. Still, it's misleading at best.

I don't know anything about this binary search version. When I was a kid, we used to play a "Guess …

With two for loops, one nested inside the other. The outer for loop manages the rows, and the inner for loop manages the variables for the columns inside the row being printed.

Remember that the total width of the diagram, minus the number of stars you print on that row, is the number of spaces that must be printed on the row.

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 …

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 …

An odiferous reminder ===> perfect! ;)

Welcome to the forum, Str91! ;)

The way programming forums work is, you get the ball rolling on the assignment, and then come back when you can describe a particular problem - preferably by posting code and asking specific questions about whatever is the problem.

That saves us a boatload of time in helping, and it keeps the forum from being inundated by students wanting their homework done, with minimal effort (not saying you are doing that, just that it's human nature to want to).

I suggest taking some coins, on your counter/desk top, and stacking them into the physical queue and stacks you are working with, and note the pattern that you make as you move the coins from the queue, into the two stacks. Forget about the data structure part of it, for now.

After you REALLY have the queue --> two stacks part sorted out, then start your program. [steps on soapbox]:

In woodworking, they say "Measure twice and cut once". In programming it's "Study & plan, then you can"**. If you do not know every small detail to solve a problem, then you can't teach the computer to solve it.

OK, they don't say it, but they say what it conveys, and SHOULD say it. ;)

There is realloc(), but it's not available for declared arrays, just allocated ones. But you can malloc or calloc a new array, and then transfer the old, into the new array, yourself. Doing it yourself, gives you a better chance at understanding the process - good for a student. No doubt realloc() is handy, of course, so maybe you want to start out with an allocated array, instead of a declared one?

From the Pelles C help file:

Purpose:
Changes the size of an allocated object.

Syntax:
void * realloc(void *ptr, size_t size);

Declared in:
<stdlib.h>

Description:
The realloc function deallocates the old object pointed to by ptr and returns a pointer to a new object that has the size specified by size. The contents of the new object shall be the same as that of the old object prior to deallocation, up to the lesser of the new and old sizes. Any bytes in the new object beyond the size of the old object have indeterminate values.

Whoa!

This is no way to code! Take a break from the keyboard and learn how to work with arrays a bit more.

This:

char* stringArray3 = (char *) malloc (sizeof(char));;
   free(stringArray3);

Is mind-numbing stuff. After you free an array, it's GONE to Byte Heaven (or Hell), and it ain't coming back. ;)

You know you have allocated just ONE char, right? Even a 1 char string array needs two char elements in the array to hold it - one for the char, and one for the end of string marker: '\0', that all strings in C MUST have.

@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!!

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.

"Get it to work right", is THE most vague description of the problem!

C'mon! Put some specifics into it. FCOL!

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.

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

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

You only need two for loops, one nested inside the other.

The outer for loops handles how many rows, and the inner for loop handles the printing on that row.

for(r = ....etc ) {
   for(c = ....etc ) {
      with every loop you'll either add or subtract one or two to the r
      variable, which is quite nice, because it relates closely with how many 
      stars to print up in that row. 
   }
}

I usually use two int variables, "r" and "c" or "i" and "j" for this. Laid out like the above pattern, it's not too tough. All that other code is ready for the dustbin. You can see how hard it is to code up a simple assignment, when you don't have a plan.

Since our pattern repeats but in an upside down way, you may want to do half of it, and then do the other half, in a second nested pair like the first, but with different logic.

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.

Why not change the sscanf() format to %lf for the doubles you want (leave the %s for the name alone of course), and then change char dat0[][] to double data0, and see!

Extremely high probability of success (as in I've already tested it to be sure, but I didn't want to give you the ENTIRE answer).

I'm feeling a lessening of sweat equity on this program, from the OP.

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.

The value of a variable assigned the return value from a function - when there is no value returned (if I understood your question OK), will remain unchanged, but it's easy enough to test it - and don't be afraid to do that.

Different compilers, and computers, are NOT the same, and there are LOTS of differences which are still OK with the standards for C. They're undefined, and so almost anything is allowed.

You're using A[pivot], instead of using the value of the pivot itself. When I do that, my Quicksort crashes as well.

Look again at the code I posted - pivot is a value, not an index.

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 …

Try <= in your comparisons. Without at least one of them in in that if statement, my version of Quicksort, goes into an endless loop.

/* 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);

I have to say, naming a variable "big" when it has to be incremented repeatedly, and naming another "small" when it can only be decremented, is some crazy naming scheme. I'd swap those two names, just for a bit more clarity.

Some food for thought:

/*
7
aluminum .012580 .003000 32. 1130.
cast-iron .005441 .001747 32. 1160.
ingot-iron .006375 .001636 32. 1380.
malleable-iron .006503 .001622 32. 930.
ingot-steel .006212 .001623 32. 1380.
copper .009278 .001244 32. 1160.
nickel .007652 .001023 32. 1830.
*/

#include <stdio.h>

int main(void) {
   FILE *fp;
   int i, rowNum;
   char buff[100];
   char name[50][30];   //use malloc or a linked list, to get just what you need, later on
   char dat0[50][30];   //use a struct to unite name and data, later on
   char dat1[50][30];   //so you have one array of structs.
   char dat2[50][30];
   char dat3[50][30];

   if((fp=fopen("metalData.txt", "r")) ==NULL) {
      printf("Error: metalData file did not open!\n");
      return 1;
   }
   
   fscanf(fp, "%d",&rowNum); printf("rows:%d\n", rowNum);
   fgetc(fp); //most necessary, removes the newline char fgets won't do that for you
   
   for(i=0;i<rowNum;i++) {
      printf("\n");
      //get and print the first line of data
      fgets(buff, sizeof(buff), fp); printf("%s", buff); //get one row in the file
      //pull the data into separate arrays, and print them
      sscanf(buff, "%s %s %s %s %s", name[i],dat0[i],dat1[i],dat2[i],dat3[i]); printf("%s %s %s %s %s\n",name[i],dat0[i],dat1[i],dat2[i],dat3[i]); getchar();
   }
   printf("\nEeach row of metal data should be printed twice, and have the same content\n");
   fclose(fp);    
   printf("\n");
   return 0;
}

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 …

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

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

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.

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.

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; …

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.

What was the time?

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!

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: 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?

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.

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(); …

@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 …

You can use a for loop. Say you want to work through 3 sorting functions, with two different sorting sizes.

for(i=0;i<6;i++) {
   if(i<3) ram2get = 10000 else ram2get = 1001001
   allocatemem(ram2get);
   genRandomNums(ram2get);
   

   if(i==0 || i==3) bubblesort();
   else if(i==1 || i==4) Combination();
   else if(i==2 || i ==5) Insertion();
   
   //this will be executed every time thru the loop
   OK=verifyAccuracy();
   if(OK) print No error found. else print Error!
   displayStats();
   etc.
}

Selection sort will always have the fewest comparisons, btw. That is the only reason it exists. What is a "Combination Sort"?

Wrong format. Use:

filePointer = fopen("filename", "w");

Your file mode letter can be "r", "w", "a" "rt", "wt","rb" or "wb". The one's with a b are for binary mode, t is for text (and your system may have a default set by a variable option for your system). You can also use + between the letters, etc.

You should check your filePointer to be sure it's not NULL after the open line of code. It's common to have a filename be just a letter off, etc. Filenames are case sensitive, btw.

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 …

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 …