Posted by: geodesic
## c prime # generator - 04/18/04 11: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?

#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 12:16 PM

well i solved it in this manner

#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 02:29 PM

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.

#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 04:12 PM

outstanding silentrage !!

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

G

Posted by: Gremelin
## Re: c prime # generator - 04/18/04 04:51 PM

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/29/04 06:38 AM

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/31/05 04:05 AM

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.