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.

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

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.

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.

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.

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

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.

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

I would creat an array with the first 100 prime numbers then use a sieve method. Sieve of Eratosthenes

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.

No, it isn't allowed. That code will not compile for the reson you've stated.

Quzah.

http://mathworld.wolfram.com/PrimeNumber.html

formulae for prime numbers. with the exception of 2 and 3 but you can manually check for that.

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.

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.