c prime # generator

Posted by: geodesic

c prime # generator - 04/18/04 03:37 AM

hello.

so far i have this program to generate the prime numbers (numbers whose only factors are 1 and themselves) between 1 and 100.

what's wrong with this picture?
Code:
#include <stdio.h>

main
{
  int i,j,k,l=0;
	
	for i=2; i<=20; ++i
	{
	   for j=1; j<=i ; ++j
	   {
	     k = i%j;
	    
            if k == 0 
	    { l = ++l; 
	    }  
	    if l == 2
            {printf "%d is a prime \n",i
            }       
           }
        } 
	
	return 0;
}
thanks for the tips / suggestions

G
Posted by: geodesic

Re: c prime # generator - 04/18/04 04:16 AM

well i solved it in this manner
Code:
#include <stdio.h>

int main(void)
{
	int i,j,l=0;
	
	while i <= 100
	{
	   l = 0;
	   
	   for j=1; j<=i; j++
	   {
	    if i%j == 0
	    {
	     l++;
	    }
	   
	   }
	   
	   if l == 2
	   {
	    printf "%d is a prime number\n" , i;
	   } 
	   
	   i++;
	}  
	
	return 0;
}
rather brutish etc. is there any way to stremline it .. like any way to use for loops instead of the while ...

thanks

G
Posted by: SilentRage

Re: c prime # generator - 04/18/04 06:29 AM

I've changed the while into a for like you asked, and also made the algorithm twice as fast by skipping the evaluation of even numbers which are all non-prime. Actually it's more than twice as fast with several other optimizations I made.

Code:
#include <stdio.h>

int main(void)
{
    int i=0,j=0,l=0;

    printf("1 is a prime number\n");
    printf("2 is a prime number\n");

    for (i=3; i < 101; i=i+2)
    {
        l = 0;

        // skip 1, don't go as high as i
        for (j=2; j<i; j++)
        {
            if (i % j == 0)
            {
                l++;
                // we already know it isn't prime
                break; 
            }
        }

        if (l == 0)
        {
            printf("%d is a prime number\n", i);
        }
    }

    return 0;
}
Posted by: geodesic

Re: c prime # generator - 04/18/04 08:12 AM

outstanding silentrage !!

that is MUCH faster and more elegant. thank you very much !!

G
Posted by: Gremelin

Re: c prime # generator - 04/18/04 08:51 AM

I edited the original posts, mainly to add the code tags so that formatting was done properly.

Thanks for the code though, we were actually toying with some encryption a while ago ...
Posted by: ninjaneo

Re: c prime # generator - 04/28/04 10:38 PM

When I made my prime generator, I did it a different way...

If you take your range of numbers... lets say 20, starting with one. go like so...

Well, we know 1 is a prime. so skip that.
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

(things that we've called primes are in bold, composites are in italics)

now, we will eliminate every multiple of 2.

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

ok, now we see that three is the next prime (because its the next not elimanated number).
So, lets kill multiples of 3.

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

mmk, Most of those we already eliminated - but so what.

5 is next

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

ok, well that didn't do much.

Well, now that its 11's turn and that is more than half of the range of numbers (20/2==10) there is no reason to check the rest.

Any non-eliminated number is prime.

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

hmmm... those italics didn't show up very well... oh well.
Posted by: fortytwo

Re: c prime # generator - 03/30/05 07:05 PM

I just stored the primes in an array as I found them. To find them you just see if the number can be divided by any of the primes you have already found.