C++ question on prime numbers.

Question

Hello. I am trying to make a program that determines if the number is prime or composite. I have gotten thus far. Could you give me any ideas so that it will work? All primes will , however, because composites have values that are both r>0 and r==0, they will always be classified as prime. How can I fix this?

int main()
{
    int pNumber, limit, x, r;               
    limit = 2;
    x = 2;

    cout << "Please enter any positive integer: " ;
    cin >> pNumber;

    if (pNumber < 0)
    {
        cout << "Invalid. Negative Number. " << endl;
        return 0;
    }
    else if (pNumber == 0)
    {   
        cout << "Invalid. Zero has an infinite number of divisors, and therefore neither composite nor prime." << endl;
        return 0;
    }
    else if (pNumber == 1)
    {
        cout << "Valid. However, one is neither prime nor composite" << endl;
        return 0;
    }
    else
    {
        while (limit < pNumber)
        {
            r = pNumber % x;
            x++;
            limit++;

            if (r > 0)
                cout << "Your number is prime" << endl;
            else 
            {
                cout << "Your number is composite" << endl;
                return 0;
            }
        }
    }

    return 0;
}

Answer 1

Check out http://en.wikipedia.org/wiki/Prime_number and http://en.wikipedia.org/wiki/Primality_test

The simplest primality test is as follows: Given an input number n, check whether any integer m from 2 to n − 1 divides n. If n is divisible by any m then n is composite, otherwise it is prime.

Answer 2

For one thing, you'll want to break out of your loop when you find some x where pNumber % x == 0. All you need to do is find one factor of pNumber greater than 1 and less than pNumber to prove it's not prime -- no point in searching further. If you get all the way to x = pNumber without finding one, then you know pNumber is prime. Actually, even if you get to the square root of pNumber without finding one, it's prime, since if it has a factor greater than that, it should have a factor less than that. Make sense?

Answer 3

I don't know what you have been taught thus far, but my discrete mathematics teacher was a fan of the Miller-Rabin test. It is a pretty accurate test that is very easy to code, within a few base tests you have a very negligible chance that you have a Carmichael Number. If you haven't gotten that far in your studies I would just stick to some basic division rules for numbers.

Answer 4

#include <iostream>
#include <math.h>
// Checks primality of a given integer
bool IsPrime(int n)
{
    if (n == 2) return true;
    bool result = true;
    int i = 2;
    double sq = ceil(sqrt(double(n)));
    for (; i <= sq; ++i)
    {
        if (n % i == 0)
            result = false;
    }
    return result;
}
int main()
{
    std::cout << "NUMBER" << "\t" << "PRIME" << std::endl;
    for (unsigned int i = 2; i <= 20; ++i)
        std::cout << i << "\t" << (IsPrime(i)?"YES":"NO") << std::endl; 
    std::cin.get();
    return 0;
}

Answer 5

bool check_prime(unsigned val) { 

    if (val == 2)
       return true;

    // otherwise, if it's even, it's not prime.
    if ((val & 1) == 0)
        return false;

    // it's not even -- only check for odd divisors.
    for (int i=3; i*i<=val; i+=2)
       if (val % i == 0)
           return false;

    return true;
}

Answer 6

Simplest method is for a given number n , if it is perfectly divisible with any number between 2 to sqrt(n), its a composite, or else its prime