prime number.

• 05-11-2004
tdoctasuess
prime number.
ok im in this call for c programing. and the newest assignment is this.

Write a program that inputs a number and determines whether the number is prime. After displaying the results, ask the user if they want to try again. At the end, print "Have a nice day!". Sample output:

Enter number: 25
The number 25 is not prime.
Continue? (y/n) y
Enter number: 17
The number 17 is prime.
Continue? (y/n) n
Have a nice day!

this assignment is really screwing me. i need help bad. if you could send me the program in the simplest terms possible so it looks like a beggining student could have written it i would be very greatful. thanks.
• 05-12-2004
kinghajj
I don't know how to test primes, so check google.

Code:

```#include <stdio.h> int TestPrime(int n) {  ... your code here ... } int main() {     char continue = 'y';     int number;     while(continue == 'y')     {         printf("Enter Number: ");         scanf("%i", &number);         if(TestPrime(number))         {             printf("%i is prime\n", number);         }         else         {             printf("%i is not prime\n",number);         }         printf("Do you want to continue? [y/n] ");         continue = getc();     }     return 0; }```
So, you just need to find out how to get TestPrime to work
} :p
• 05-12-2004
Rouss
To test a number for primeness (??), just try looping through all the values between 2 and that number, and mod (%) the number in question by the loop variable... If it is equal to 0, then it can't be prime.
• 05-12-2004
major_small
you would need 2 nested loops... your example won't work... take 9 for example, not prime, but your algorithm says it is because it never tests 3*3, only 2*9,3*9,4*9, etc.

the first loop increments the first operand, and the inner loop increments the second.
• 05-12-2004
Thantos
Code:

```int isdiv(int dividend, int divisor) {   return (dividend % divisor) == 0; } int isprime(int num) {   int i;   i = 2;   while (((i * i) < num) && (isdiv(num, i) == 0))     ++i;   if (i * i > num) return 1;   else return 0; }```
Copied from http://www.drtak.org/teaches/ARC/cis.../proj3/prime.c
That is a C code equivlent for an assembly homework we had to do. As such it really doesn't really need to be broken into two functions.
• 05-12-2004
vsuchi
If input_number is the input number,

for( i = 0; i < input_number/2; i++)
{
if (( input_number % i) == 0)
{
printf( "not prime number ");
break;
flag = false;
}
}

if ( flag != false)
printf( "The number is prime");

This the code for checking the prime number
• 05-12-2004
Deckard
I recently worked on a prime number generator here at work (I cannot share the code with you). I just wanted to point out that after you test the number against 3 (n % 3), you only need to test odd numbers after that. So, start at 2, go to 3, then increment by two each time after that. It will make your code much faster.

Also, you only need to check odd numbers (besides 2) up to the square root of the number you're testing (not all the way up to the number itself).

I hope that helps.
• 05-12-2004
Rouss
Quote:

Originally Posted by major_small
you would need 2 nested loops... your example won't work... take 9 for example, not prime, but your algorithm says it is because it never tests 3*3, only 2*9,3*9,4*9, etc.

the first loop increments the first operand, and the inner loop increments the second.

I think you referring to my post.

But I didn't say to multiply, I said to mod.
So when it tested 9, the loop should go like this:
Code:

```9 % 2 = 1 9 % 3 = 0 (return some indication that it is not prime, 0 perhaps```
As for a prime such as 11, let's say. It would iterate through the entire loop, never having 11 % i (iterator) == 0, so when it exits the loop, just return 1 or some other indication that it is prime.

I hope I was more clear this time. I think that what I have said works, if not, please let me know.

Also, Deckard made some very good points. I would say test num % 2, before the loop, then start the loop at 3, and increment by 2... I guess sqrt() would be good to throw in there since it will make it faster.

Rouss
• 05-12-2004
linuxdude
I would creat an array with the first 100 prime numbers then use a sieve method. Sieve of Eratosthenes
• 05-12-2004
barim
I just want to point on this part of codes written by kinghajj char continue = 'y';

continue is reserved keyword, so is it allowed for naming variables? I know so far that it is not allowed. Anyway kinghajj has good suggestion for this kind of problem.
• 05-12-2004
quzah
No, it isn't allowed. That code will not compile for the reson you've stated.

Quzah.
• 05-12-2004
sand_man

formulae for prime numbers. with the exception of 2 and 3 but you can manually check for that.
• 05-13-2004
laserlight
So far it looks like you're just going to use trial division, and it'll be on fairly small primes.

The fastest testing when using trial division is when only prime numbers up to the square root of the given integer is used to test.

So a simple idea is to calculate (or pre-calculate) an array of primes, then test from 2 to the last prime in that array, or stop when the integer is shown to be composite.
If the test number is within the range of this array, you could also use say, binary search instead of trial division, i.e. not found means composite.

There is a little bit of cheating that might be involved though, since it would be advantageous to at least pre-calculate the size of the array, if you dont want to pre-calculate the whole array.
The array itself could be obtained easily by using a sieve such as the Sieve of Eratosthenes, as mentioned earlier.
• 05-13-2004
caroundw5h
I recently did submitted some code about primes here . it was a more efficent method of finding primes. saved a lot of time. You can see the basic idea in the code and then add kinghaji if/else clause to terminate or continue the program.
Good luck.