2

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;
}
Alconja
  • 14,834
  • 3
  • 60
  • 61
Sagistic
  • 683
  • 2
  • 9
  • 16
  • You might want to add a check for even numbers right off the bat to speed things up something like if( num % 2 == 0), then you could have your loop go up by twos instead of ones. Also there are lots of nifty tricks for finding primes, 5 is pretty easy since the number ends in a 0 or a 5, numbers divisible by 3 have digits that when added up are divisible by 3. Your best bet would be to eliminate the really easy to check ones first. – Maynza Mar 08 '10 at 03:25
  • @Maynza Numbers don't really end in 5. It's just that their decimal representation ends in '5'. To use that kind of check, you would need to first convert your integer to a string, or somehow build a list of its digits. In this case, you could get the user input as a string, do those two checks, then convert it to an integer for all the other checks. But it's more work, and I don't know if it will be any faster. – Tyler Mar 08 '10 at 03:33
  • 2
    No you wouldn't, just check (num % 10 == 5). – Maynza Mar 08 '10 at 03:37
  • instead of "while (limit < pNumber)" use "while (limit <= std::sqrt(pNumber)+1)" –  Mar 08 '10 at 04:20
  • many dupes http://stackoverflow.com/questions/627463/how-can-i-test-for-primality http://stackoverflow.com/questions/2055300/primality-check-algorithm – N 1.1 Mar 08 '10 at 05:00
  • @Maynza: you forgot `|| num % 10 == 0`. Or be smart and write what you actually meant: `num % 5 ==0 `. That's not a nifty trick at all. It also works for `num % 37 == 0` And `num % 600000001 == 0` – MSalters Mar 08 '10 at 14:25
  • @MSalters: You are right, but you don't really learn anything if you do it that way, I just happen to think it is fun to analyze numbers and see certain patters emerge. – Maynza Mar 08 '10 at 15:01
  • @Maynza: the problem is that there are real patterns in the numbers, but they're in binary. E.g. there is a nifty trick to check for division by 11. That happens to work for all values of 11 ;) - both binary 11 and decimal 11. It involves summing all the digits in odd and even position and checking whether they are equal modulo 11. E.g. 1001 is divisible because 1=1. (in all bases!) – MSalters Mar 08 '10 at 15:46

8 Answers8

3

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.

Pierre-Antoine LaFayette
  • 24,222
  • 8
  • 54
  • 58
  • 5
    You only need to check up to sqrt(n). – Maynza Mar 08 '10 at 03:19
  • Simplest. Agreed. But complexity can be considerably reduced using Deterministic Miller-Rabin Primality check. – N 1.1 Mar 08 '10 at 04:56
  • @nvl: the number being tested is an `int`. Miller-Rabin is massive overkill, and I'm not sure it's even faster on a 32bit int. An algorithm which relies on the Riemann Hypothesis for its correctness is barely worth mentioning to someone who's struggling to write their first ever primality test correctly ;-) – Steve Jessop Mar 08 '10 at 13:22
  • @steve jessop: hmm may be :). Atleast, he should know that prime numbers are of the form 6k+1, 6k-1. (~ 2,3) – N 1.1 Mar 08 '10 at 13:50
1
#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;
}
Rajendra Uppal
  • 19,218
  • 15
  • 59
  • 57
1
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;
}
Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • This function thinks 4, 8, and 10 are prime numbers. – M Perry Mar 08 '10 at 10:21
  • @M Perry: oops, that's what I get for typing code in without testing it. I missed a set of parens (now fixed). Thanks for pointing it out. – Jerry Coffin Mar 08 '10 at 14:18
  • It also thinks 1 is prime, but anyone passing 1 into a primality check probably deserves what they get. – Steve Jessop Mar 08 '10 at 14:26
  • 1
    @Steve: Returning a bool restricts us to a yes/no answer, and for 1 there isn't really one -- for some purposes, it's convenient to treat it as prime, others as composite, and still others as neither one. "Neither" is most common, but hardly the only answer. – Jerry Coffin Mar 08 '10 at 14:36
  • That's what I mean by "deserves what they get", it's a bit like asking whether the natural numbers start from 0 or 1. I have a maths degree, though, so as it happens I've been trained that 1 is not prime. This makes the definition of a prime longer, and the statement of the fundamental theorem of arithmetic shorter. I've never seen 1 stated to be composite, that I remember. In ring theory there's the concept of "units", which are explicitly excluded from being either prime or irreducible. The concept is nearly degenerate for the integers, though, since there are only two units (1 and -1). – Steve Jessop Mar 08 '10 at 14:47
1

with respect ur code u didn't check if i enter 2 what will be happened, and also u didn't return any thing if it is prime....thats why it is always returning prime in spite the number is composite . here is the code below =>

#include<iostream>
using namespace std;
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 if (pNumber == 2){
        cout << " Your number is prime" << endl;
        return 0;
    }
    else{
        while (limit < pNumber){
            r = pNumber % x;
            x++;
            limit++;

            if (r > 0){
                cout << "Your number is prime" << endl;
                return 0;
            }
            else{
                cout << "Your number is composite" << endl;
                return 0;
            }
        }
    }
    return 0;
}
Saikat Kundu
  • 350
  • 1
  • 15
0

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?

Tim Goodman
  • 23,308
  • 7
  • 64
  • 83
  • The key point is you have the right idea that `r==0` shows you it's not prime . . . but if you don't *stop* when you find some `r==0`, and instead keep going and overwrite it with some `r!=0`, then you're throwing out the proof that it's not prime and mistakenly marking it as prime. – Tim Goodman Mar 08 '10 at 03:23
  • yea, I'm having trouble on the stopping part. How am I suppose to break on that. – Sagistic Mar 08 '10 at 03:28
  • 1
    You almost answered your own question. Look up the keyword `break`. – Tyler Mar 08 '10 at 03:31
  • lol, I know your supposed to use break, however, I'm not sure how. I've edited to script, but now its declaring all the primes b4 it tells u that its a composite. lol – Sagistic Mar 08 '10 at 03:34
  • The line where you tell it to cout<<"Prime" is used anytime r > 0, which doesn't necessarily mean it was prime, only that the number you tried to divide it by didn't go in evenly. – Maynza Mar 08 '10 at 03:43
  • yes, so when i input a number like 13, it'll display "your number is prime" 12 times.. haha.. let me try to fix that – Sagistic Mar 08 '10 at 03:47
0

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.

Maynza
  • 748
  • 5
  • 18
0

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

Kazoom
  • 5,659
  • 16
  • 56
  • 69
-2

Hi i have done this that also without using math.h header file....Have used turboc compiler. Following program checks whether the number is prime or composite.

                   #include<iostream.h>
                   #include<conio.h>
                   class prime
                             {
                                int a;
                                public:
                                     void check();

                             };
                             void prime::check()
                                                 {
                                                      cout<<"Insert a number";
                                                      cin>>a;
                                                      int count=0;
                                                      for(int i=a;i>=1;i--)
                                                         {
                                                            if(a%i==0)
                                                                    {
                                                                      count++;
                                                                     }
                                                         }
                                                             if(count==1)
                                                                      {
                                      cout<<"\nOne is neither prime nor composite";
                                                                       }
                                                             if(count>2)
                                                                       {
                                      cout<<"\nThe number is composite " ;
                                                                       }
                                                             if(count==2)
                                                                       {
                                      cout<<"\nThe numner is prime";
                                                                       }
                                 }

                                void main()
                                          {
                                            clrscr();
                                            prime k;
                                            k.check();
                                            getch();
                                          }
Deepeshkumar
  • 395
  • 3
  • 13