Prime Number?

Hi guys,
I am pretty new to C and I need a little help. I am trying to write a program to determine a prime number for my class lab. I am a little confused to say the least and was wondering if anybody could help me. I just want an idea of how to get this thing going. Could someone break it down for me. I feel like a moron!!!

Thanks,
Joe

Let me try...

Firstly you have to know how you would determine a prime number logically, ie come out with an algorithmn, just a simple one that you would normally use to work out if using paper and pencil...

I think the simplest is something like this (correct me if I am wrong):

A number is prime if its not divisble by all the (positive) numbers before it (except 1 of course).

With that you can start translating it to code. Of course the algorithmn is really inefficient, but the main thing would to get it to work first and then try to optimize it later...

Hope that helps.

Good luck

Here is an efficient algorithm to find prime numbers.

klausi

ok I have a little code here. It doesnt work but I think I have the right I idea. It basically tells me that every # is not prime except for the # 1. Here goes nothing:

Its a function and the prime is being passed in:

char test_prime(int prime)

{

int r; /* the remainder*/
int i; /*the numbers up to the prime*/

for(i=2; i<prime;i++)

r = prime % i;
/*basically what i want it to do is take all of the numbers greater than 2 and up to the prime and mod them. If the remainder is equal to zero then it will not be prime, right? */

if(r == 0)
{
return('n'); /*not prime*/
}
else
{
return('p'); /*prime*/
}

}

Thanks guys,
Joe

I didn´t compile it, but it should work.
You can make it more efficient if you write

Code:

---

for(i=2; i<sqrt(prime)+1;i++)

---

I don´t know if the name for the function to get a square-root is really "sqrt", but I think so.
You have to include <math.h> into your code, to use the sqrt() function.

klausi

Your code doesn´t work, but I know that it has been corrected by another one.
klausi

Hmm...actually

Try this

// first check if number is even; if so not prime
if(!prime%2)
r = 1;

// then check every odd number
for(i=3; i<sqrt(prime) + 1 && !r; i+=2)
if(prime%i)
r = 1;

You only check if the number is odd, so I guess it more efficient.

Of course you have to check the speical case when:

prime == 2

Your code does not work

[code]
char test_prime(int prime)
{
int r; /* the remainder*/
int i; /*the numbers up to the prime*/

for(i=2; i<prime;i++)
r = prime % i;
if(r == 0)
{
return('n'); /*not prime*/
}
else
{
prime could still not be prime here, 15 is not
divisible by 2 but is not prime.
return('p'); /*prime*/
}
}

Also remember that 1 is not prime.

Try this:

#include <stdio.h>

main(){
int primetested,numberofprimes, primesfound, x;

printf("Enter the number primes you want: ");
scanf ("%d", &numberofprimes);

printf("1 is prime\n");

primesfound = 1;
primetested = 3;

while (primesfound < numberofprimes){
x = 2;

while (primetested > x){

if (x != primetested && primetested % x == 0){
break;
}
x++;
}

if (x == primetested){
printf("%d is prime\n", primetested);
primesfound++;
}
++primetested;
}

return 0;
}