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.

[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.

[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.

[iMalc]

It still tests against all even numbers greater than or equal to four.
I.e It only goes up by two at a time in the outer loop.

[st00ch]

ok i've taken the suggestions in and changed the code.
i got the scrap book out and wrote down a flow diagram and then worked out the the code, adding the square root idea and incrementing by 2 idea in.

i try to compile but i get lots of errors still. but it's close.

#include <stdio.h>
#include <math.h> /* included for sqrt() function */
main()
{
int p,prevprime,root,count,max;

count=0;
p=3;
prevprime=0;
FILE *fwrite;
fwrite=fopen("/home/primes.txt","a+");  /*adds to the end of file */

FILE *fread;
fread=fopen("/home/primes.txt","r");  /*reads values of file */

root=sqrt(p);

printf("Enter how many primes to find:");
scanf("%d",&max);

while(max<=count)
{count++

while(prevprime<=root)  /*First logic argument checks previous prime value isn't greater then root value of p, since p divided by previous prime values (no greater than root) are the only ones needed to be checked*/ 
{if((prevprime%p)==0) /*2nd logic argument check if p is actually a prime value */ 
 {printf("not a prime:%d\n",p); /* not a prime... dang */
  fclose(fread);       /*closes file so it will read from start next time */
  prevprime=0;      
  p=p+2;            /* incrementing up by 2, primes are only odds */
  root=sqrt(p);     /* new root value when new p value*/
 }
 else{fscanf(fread, "%d" &prevprime); /* changes preprime value so it can be checked again by 1st and 2nd logic argument */ 
      printf("prevprime value:%d",prevprime); /* i just want to see the preprime value to check whats happening */ 
     }
}
fclose(fread);
printf("Prime:%d\n",p);   /* YAY prime number found*/
fprintf(fwrite,"%d\n",p);     /* calls primes.txt and adds value at end of file */
p=p+2;         /* incrementing up by 2, primes are only odds */
root=sqrt(p); /* new root value when new p value*/
prevprime=0;  /* resets preprime value for logic arguments */
}
printf("finnished finding %d primes", max);

}

[Adak]

i try to compile but i get lots of errors still. but it's close.

Of course, it would be nice to see what those errors were! <hint, hint>

A few suggestions:

1) ALWAYS int main(void) or int main(int argc, char *argv[]), and return 0 at the end of main.

2) The whole writing to the file, while reading from the file, and re-closing and opening the file - that part I'd dump. Put the primes you find, into a file, AND IF YOU WANT TO, keeping the last (most recent) big bunch of them (maybe 1,000 or 100,000 or whatever you think is a reasonable number. It depends on how many primes you're going to be generating), into the array.

For example, using the basic strategy outlined in your code, you'll generate the first 1,000 prime numbers, in a second or so (maybe less, depending on your system). So being practical, although using the previous array is a big speed up, how much time do you want to spend optimizing the program, to save a half a second?

3) The number two is a prime number (one is not but two is). So don't leave out 2.

4) So I would suggest opening the file in write mode, only. Not append, and not for reading, either.


5) Take an example of a prime: 101 - the previous prime will be WAY more than 10, which is the square root of 101 (about). previous primes should work down starting with the square root of the number being checked, and going down, or working from a very low prime like 5, and working upward.

I don't get the whole previous prime logic, and I can't tell what "count" is counting.

You have the two nested loops, and the basic idea, but I can't quite tell whats up with the logic in them.

[iMalc]

I don't feel like trying to read such badly formatted code today. Don't start each line on the same line as the curly bracket, and indent each line according to how many braces it is within.