1,000,000 prime numbers.

I am a programming newb, and am writing a program in C that calculates and displays all primes from 1 to n.
If I calculate all primes from 1 to 15,485,863. (the 1,000,000th prime)
it takes 26 seconds on a MacBook with OSX.
I've been trying to optimize it as I go. at first, it took me 1 minute to get there.
do you reckon this is any good?

Also, for some reason, when I reach the prime with value of about 18,000,000 my program starts to go haywire and go extremely quick, and reaches the prime with value 58,000,000 in about 2 seconds, of course, missing most primes in the way.
I am still pretty new, and have been browsing for a while trying to find a solution, and can't find any.
Any tips would be greatly appreciated.

Not much we can do without seeing the code.

I can't figure out how to post code with it not loosing it's shape.
anyways, I think I figured out my problem.
I was using a floor function to check if it is not a whole number, because % wasn't working. I guess the floor() just wasn't accurate enough.
it now goes the first mill in 15 seconds and keeps going perfectly Thanks though. will post if I have any other problems.
Edit: 6 seconds now

I think there's a [*code][*/code] tag you can use.

Also, http://pastebin.com/

What language is it written in? For something like this I'd recommend writing in Asm, and designing it in a way which is already optimized. (For example, use shifts for multiplication/division, rather than the MUL and DIV calls)

Originally Posted by Vero

Also, http://pastebin.com/

This.

Calculating speed can also depend on hardware. I could try it on my i5 arriving in a few days, I reckon it would easily hit under 10 seconds. Don't you just love cheap, overpowered processors?

#include<stdio.h>
main()
{
  int n,count=0, a,first,last;
  printf("first ");
  scanf("%d",&first);
  printf("last ");
  scanf("%d",&last);
  /*Just so that all integers can be inserted without problem, 
    since I'm using a loop that depends on where you start*/
 while((first-7)%30 != 0)
    {
      first=first-1;
    }
 if(first<=7)
   {
     first=7;
     count=4;
     printf("2 3 5 7 ");
   }
   
 n=inicial;
 /*actual progrqm starts here*/
 while(n<final)
   {
     
     n=n+4;
     a=7;
     
     while(a*a<n&& n%a!=0)
       {
	 a=a+4;
	 
	 if(a*a<n&& n%a!=0)
	   {
	      a=a+2;
	      
	      
	      if(a*a<n&& n%a!=0)
		{
		  a=a+4;
		  
		  
		  if(a*a<n&& n%a!=0)
		    {
		      a=a+2;
		      
		      
		      if(a*a<n&& n%a!=0)
			{
			  a=a+4;
			  
			  
			  if(a*a<n&& n%a!=0)
			    {
			      a=a+6;
			      
			      
			      if(a*a<n&& n%a!=0)
				{
				  a=a+2;
				  
				  
				  if(a*a<n&& n%a!=0)
				    {
				      a=a+6;
				      
				    }
				}
			    }
			}
		    }
		}
	    }
	}
      if(a*a>n)
	{
	  printf("%i ",n);
	  count=count+1;
	}
      /*repeat with n=n+(2, 4, 2, 4, 6, 2, 6)* It would be a huge post if I post every single one*/
    }
  printf("\n\ncount = %i\n",count);
}

Thanks for the help!
That's my fastest code so far in case anyone is interested. Tested it till prime with value 2,000,000,000.
I want to make it much more efficient, but am having trouble making it much better than it is.

make the thing skip multiples of 2, 3 and 5
for the present term make it stop checking after you get to the number which is it's square root.

Originally Posted by nighthawkx

make the thing skip multiples of 2, 3 and 5
for the present term make it stop checking after you get to the number which is it's square root.

Already does that
I want to make it skip up to multiples of 11 but I haven't figured out how to do that in a short decent way.

Rewrite in Asm. Use only bit-shifts and addition. Go go go.

Originally Posted by nighthawkx

for the present term make it stop checking after you get to the number which is it's square root.

Then you need to call for that on every check, no? That seems quite tedious.

Originally Posted by 8-bit

Then you need to call for that on every check, no? That seems quite tedious.

Its a linear cost for ~quadratic savings (for sufficiently small numbers at least; the ratio between primes less than root(n) and greater primes less than n will eventually accede 1:2*); running two functions for each of ten checks is preferable to running one on each of a hundred.

As for the problem at hand, 3h, I see three options:
The first and no doubt least helpful would be to continue as you are and simply expand your incrementalization process: with a serious effort and some auxiliary code you could reasonably accept start values of n(2*3*5*7*11)+13.

The second would be to draw test divisors from your set of already confirmed primes, rather than re-generating them with each run. It should be a simple matter of having the program append to a list everything it currently prints (and then replacing your "a" generation process with a run through [first part of] the list)... but my natural fear of C++ tells me that this will be far harder than it should be.

Finally, as this seems top be a self-teaching experience and not an effort at a truly effective prime generator (I mean.. yeah) I'm guessing you might not mind starting over with a new approach.

For very large primes a "top down" method becomes more appealing. Approximate the nth prime and cushion yourself with a ~3% increase. Generate the list of integers from 2 to your ceiling. Redefine the list removing its intersection with the set of integer multiples of its (loop #) element while that element is less than sqrt(ceiling): loop. Return the nth element of your list.

Edit: *I assume. Gonna check that when I get home tonight.
Edit 2: Yeah, I was FOS sorry. The ratio approaches zero.
I got curious it worked out the incrimentalization I suggested above (skipping 7 and 11 in addition to 2, 3, and 5). In apology, here it is:

4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12

Originally Posted by 8bit

Rewrite in Asm. Use only bit-shifts and addition. Go go go.

Yeah.... umm............
.
.
.
What?

Originally Posted by mmmmm_PIE

As for the problem at hand, 3h, I see three options:
The first and no doubt least helpful would be to continue as you are and simply expand your incrementalization process: with a serious effort and some auxiliary code you could reasonably accept start values of n(2*3*5*7*11)+13.

Yeah, I might just go ahead and do that. Would make some serious modifications so that I have to type less though.

Originally Posted by mmmmm_PIE

The second would be to draw test divisors from your set of already confirmed primes, rather than re-generating them with each run. It should be a simple matter of having the program append to a list everything it currently prints (and then replacing your "a" generation process with a run through [first part of] the list)... but my natural fear of C++ tells me that this will be far harder than it should be.

Actually, just C.
Anyways, this is a nice approach, memory-wise, perhaps not so much, and by what I've learnt so far, I have no Idea how to do that. I wouldn't have to keep a list in another program even, but use the ones that are being generated by the run. I definitely should do this... whenever I figure it out.

Originally Posted by mmmmm_PIE

For very large primes a "top down" method becomes more appealing. Approximate the nth prime and cushion yourself with a ~3% increase. Generate the list of integers from 2 to your ceiling. Redefine the list removing its intersection with the set of integer multiples of its (loop #) element while that element is less than sqrt(ceiling): loop. Return the nth element of your list.

I had thought about that as well, but thought it could be very memory consuming and perhaps slower. My program calculates primes with values of 4,000,000,000 by now (without any real modifications) and shows no lag in between them. A list this long..... Scary.

Originally Posted by mmmmm_PIE

Edit 2: Yeah, I was FOS sorry. The ratio approaches zero.
I got curious it worked out the incrimentalization I suggested above (skipping 7 and 11 in addition to 2, 3, and 5). In apology, here it is: CODE

Oh... interesting. I would have made the same argument you did.
And thanks for the suggestions difference code! I am actually going to generate it myself inside another program that will attempt to spit out the prime program I actually want

I will really try to implement that "divide only by primes" instead of by the progression I'm using. Just have to figure out how.
Thanks!

Originally Posted by 8bit

Rewrite in Asm. Use only bit-shifts and addition. Go go go.



Then you need to call for that on every check, no? That seems quite tedious.

I think assembly is a just a BIT beyond his capacity, it sur as hll is ovr mne.
nah just encorportate it into the loop

while number bing checked<= rt(number being checked)
skips half the work of checking factors.

not sure if he's already done this.

Originally Posted by 3heartchallenge

I will really try to implement that "divide only by primes" instead of by the progression I'm using. Just have to figure out how.
Thanks!

set it to save your prime number results to an array, then use that array for the numbers used for division.
then at the end, have it printf the results fo the array. should save you some time there too since you'll be doing fewer memory references overall.

Originally Posted by nighthawkx

set it to save your prime number results to an array, then use that array for the numbers used for division.
then at the end, have it printf the results fo the array. should save you some time there too since you'll be doing fewer memory references overall.

Now that is just exactly what I should be doing!
I have not started working with arrays yet, but will start googling it
Thanks!

I suck at programming FYI, I tried to learn javascript when I was 12(8 years ago) and basically got over it. I know bits and pieces and the ideas to use, but...


http://www2.its.strath.ac.uk/courses...00000000000000

one possible suggestion for being a little ***** and cutting some time off from calculations, instead of have the array being written to, preinclude all the primes up until 3943 in an array
3943 *3943 exceeds your greatest term, 15,485,863, FYI.


I would thus split your program into two parts, the first part generates an array to that term, the 557th prime

print out the results from your array from there, then go onto th second half of your program and have it do calculations from there on up and have it stop checking numbers if it reaches a value in the array which exceeds the root of the number you're checking