# Prime Number?

• 03-09-2002
cprogramnewbie
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
• 03-09-2002
heljy
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
• 03-09-2002
klausi
Here is an efficient algorithm to find prime numbers.

klausi
• 03-09-2002
cprogramnewbie
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
• 03-09-2002
klausi
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
• 03-10-2002
klausi
Your code doesnīt work, but I know that it has been corrected by another one.
klausi
• 03-10-2002
heljy
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
• 03-10-2002
Unregistered

[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.
• 03-15-2002
Mitch da Man
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;
}