How to detect prime numbers?

[3vX4LyTq]

So, I'm trying to write a program where the user inputs an integer, and it determines if it is prime or composite. So far I have made it check if the number is even or odd. I have been trying to figure out how to do this for a while.

Any tips???

  int main() {

int num = 0;

int check = 2;
bool prime = true;
cout << "Check if prime: ";
cin >> num;
///actual loop
    while(prime == true){
        if (num % check == 1) {
            cout << "Prime";
            break;
        }
        else {
            cout << "This number is not prime";
            prime = false;
        }
        check++;
    }
}

[48T7M4Gy]

Search out (eg wikipedia) the Sieve of Eratosthenes.

[3vX4LyTq]

Interesting read, but I don't really know how to implement it into my code. I'm pretty new at this.

[48T7M4Gy]

I was new to it when I first saw it but to help you in practical terms I remember the Wikipedia article has pseudocode and an animation that shows how it works.

It not complicated or massive in lines and you might just be able to adapt it to what you already have. Your efforts so far aren't wasted and come back after looking at the pseudocode if you need help. Good luck with it now you're at stage II :)

[DatDankMeme]

#include<iostream>

using namespace std;

int main(){
    int n;
cout<<"Enter Number:- ";
cin>>n;
if(n==2||n==3){
    cout<<"Prime Number!";
}
else if(n==1)
    cout<<"Nor Prime nor Composite";
else if(n%2!=0 && n%3!=0 && n%5!=0 && n%7!=0){
    cout<<"Prime number!";
}
else
    cout<<"Composite";

    return 0;
}

kind of stupid but it works :p

[MZH]

A number num is prime if there is no number other than 1 and num that evenly divides it. The test for if a number check divides num is num % check == 0. If that test returns true, the number is not prime. Print "not prime" and stop the loop. Otherwise, increment check and try the next number. Just because a number is not even does not mean it is prime. If incrementing check makes it greater than or equal to num then you are done, since a number can't be divisible by a larger number. Exit the loop and print "prime".

Instead of having the bool prime variable, I would make the while condition while(check < num) and increment check at the end of the loop. There are better conditions, but make sure you understand why this one works before trying to improve it.

[integralfx]

bool is_prime( int n )
{
    if( n <= 1 ) return false;
    for( int i{ 2 }; i < n; i++ ) {
        // divides evenly,
        // not prime
        if( n % i == 0 ) 
            return false;
    }

    // otherwise, it's prime
    return true;
}

You can make it more efficient by looping until the square root of n.

[mbozzi]

DatDankMeme wrote:

kind of stupid but it works :p

Are you sure 5 is a composite number?

[lastchance]

I think I would go with integralfx's function (and definitely his following comment) for a single number test.

If I was finding not one but all the primes in a large range then the sieve-based method would be good. (This has been another topic on this forum in the recent past!)

Sorry, @DatDankMeme, but you should try your code on 121 (which is 11x11, hence not prime). Also, note @mbozzi's correction.

[3vX4LyTq]

Wow, thanks for all the help! I did it!