Prime number generator

[st00ch]

Hi all, I'm looking to generate prime numbers. the code starts with p=5, 'p' been a possible prime, then 'd' been the divisor of 'p' to check if it is a prime number or not. where 'x' just increments up changing the value of 'd'. when p/d has no remainders it then checks the value of d to see if it is/isn't equal to 1.

#include <stdio.h>
main()
{
int p,d,x;
printf("how many primes numbers do you want to find starting from 5?");
scanf("%d",&y);

p=5;
x=1;
start:
y--;
if(y>0)
{d=p-x;

if(p%d!=0)
{
x++;
d=p-x;
goto start;
}

else {if(d!=1)
{p++;
 x=1;
goto start;}

else{ if(d=1)
{printf("%d", p);
p++;
x++;
goto start;}
}}

}
}

when i compile and run it. nothing. can't be that hard.

also if omit the else's, it would still behave the same way right?

#include <stdio.h>
main()
{
int p,d,x,y;
printf("how many primes numbers do you want to find starting from 5?");
scanf("%d",&y);

p=5;
x=1;
start:
y--;
if(y>0)
{d=p-x;

if(p%d!=0)
{
x++;
d=p-x;
goto start;
}

if(d!=1)
{p++;
 x=1;
goto start;}

if(d==1)
{printf("%d", p);
p++;
x++;
goto start;}

}

}

am i doing something horribly wrong? :O

[itsme86]

am i doing something horribly wrong? :O

1) Your identation
2) Choice of variable names
3) goto

[GReaper]

1) Your identation
2) Choice of variable names
3) goto

Those are horrible for our eyes, minds and sanity, not horribly wrong for the code!

[GReaper]

@st00ch, to find if number is prime you have to do two things. Check if it's divisible by 2 or by any other previous prime number. If any of these are true, that number isn't prime.

[Adak]

You'll want some logic like this:

int max, current, i, j, num, root, noprime

get max number from user

current = i = j = noprime = 0 //we have no primes yet
num = 6    //our first number to test
while(current < max) {  //loop while we have < max primes
  root = sqrt(num) //test only up to sqrt of num (include math.h)
  for(i = 5; i <= root; i++) {  start test of num
    if(num % i == 0) {    //the actual test with modulo (remainder) arithmetic
      noprime = 1           //it divided into num evenly (no remainder)
      break;                   //so num is not a prime number
    }
  if(noprime == 0)  {    //it's a prime number
    print the number is prime
    ++current              //we have one more prime, currently
  }
  ++num;   //next number to be tested
  noprime = 0  //reset
}

This is some of the logic (not runnable code yet), that you can use to help code up your prime number generator program.

Work with this and if you have questions, post back.

[CommonTater]

int max, current, i, j, num, root, noprime

get max number from user

current = i = j = noprime = 0 //we have no primes yet

num = 6    //our first number to test

++num;   //next number to be tested

Hello Adak...
A little hint here... An even number cannot be a prime number, we know right away that it can be divided by two... so why bother even testing them?

Get the max number from the user....
Start from 3 which is the first odd prime number (1 and 2 are givens).
Increment your test value by 2 ... num += 2; ... so it stays odd the whole time eliminating the need for a "divide by two" test entirely.

[Adak]

Howdy Tater, I know the even number trick, not to worry.

It's not a ready to run program, but a scissor hoist to lift him out of the goto swamp.

[CommonTater]

Howdy Tater, I know the even number trick, not to worry.

It's not a ready to run program, but a scissor hoist to lift him out of the goto swamp.

Ahhh... yes, C's resident demon... In the 6 or so years I've been using C, I think I've used goto all of once...

[grumpy]

to find if number is prime you have to do two things. Check if it's divisible by 2 or by any other previous prime number.

Since 2 is prime, those two things to do can be expressed as one.

Additionally, to check a value is prime, it is not necessary to check divisibility by all previous primes. To check if a value is prime, it is only necessary to check if it is divisible by any primes not greater than its square root.

For example, the square root of 7 is approximately 2.64. To check if 7 is prime, it is only necessary to check divisibility by 2. It is not necessary to check divisibility by 3 or 5, since both those values exceed 2.64.

[GReaper]

Since 2 is prime, those two things to do can be expressed as one.

Additionally, to check a value is prime, it is not necessary to check divisibility by all previous primes. To check if a value is prime, it is only necessary to check if it is divisible by any primes not greater than its square root.

For example, the square root of 7 is approximately 2.64. To check if 7 is prime, it is only necessary to check divisibility by 2. It is not necessary to check divisibility by 3 or 5, since both those values exceed 2.64.

Well, ok, i didn't know that square root solution. But remember: sqrt is sslllllow!
2 may be prime but any product 2*n, n ε { 2, 3, 4, ... } isn't. If we have an arbitrary number, checking if it divides perfectly with 2 can save us a lot of CPU cycles.

[Adak]

Well, ok, i didn't know that square root solution. But remember: sqrt is sslllllow!
2 may be prime but any product 2*n, n ε (2, 3, 4, ... ) isn't. If we have an arbitrary number, checking if it divides perfectly with 2 can save us a lot of CPU cycles.

Combining these two ideas:

1) only test up to the sqr root of the number, and only find the sqr root ONCE, not every time, through the loop.

and

2) test only other prime numbers in the range of 2 through sqr root of the number. Every composite number is the product of a lower prime number.

Makes for a very quick prime number generator.

At the lower numbers, #2 doesn't help a lot - but as the primes get further apart, that #2 idea Sipher expressed above, REALLY starts paying HUGE dividends. Without it, the program will start to crawl at numbers greater than about 250,000 or so, depending on your system.

I don't believe there's a faster way to generate prime numbers, without changing over to an entirely different algorithm (like Rabin-Miller perhaps).

[grumpy]

Well, ok, i didn't know that square root solution. But remember: sqrt is ssllllow!

I didn't actually suggest computing the square root.

For example, consider which circumstances the test x < sqrt(n) and x*x < n give different results.

Even if one was to compute the square root, it only needs to be computed once, not repeatedly. And there are techniques for, reasonably efficiently, computing an integer square root.

2 may be prime but any product 2*n, n ε { 2, 3, 4, ... } isn't. If we have an arbitrary number, checking if it divides perfectly with 2 can save us a lot of CPU cycles.

We can say the same about any prime number, if you think about it. That is the underlying idea behind the sieve of Eratosphenes.

[chandanpatra]

I am also a newcomer, Just want to know whether the following will be quite faster to find prime numbers.

#include "math.h"
main()    /* This Generates Prime from 5 to 5000 */
{
 int i, j, k, s, status;
 for(i=5;i<=5000;i=i+2)             /* i holds value 5 to 5000 */
  {
    s=sqrt(i);   
    status=0;                             /* status changes if found prime */
    for(k=2; k<s; k++)               /* Second Loop checks the possibility of prime */
    {
     if(i%k==0)
      { status++; break;                /* Divisible, hence not prime */
      }
    }
    if(status==0) printf("%d,",i);   /* Prime */
  }
}

[CommonTater]

I am also a newcomer, Just want to know whether the following will be quite faster to find prime numbers.

In future, please start your own thread for a new question.
Please don't hijack running threads.

[Adak]

@chandanpatra:

Misses primes 2 and 3, and has limited range since you use just int's. Uses < square root trick and increments number by 2, so it's quick.

Display of primes needs to be improved much.

When will k=2, however, in the inner loop? You're only checking odd numbers remember.

Good algorithm, but not quite accurate yet. Needs a bit more work, imo.