Is a number prime

[neonblue00700]

Hello I got a task, and I don't have any idea how to do it. Maybe you can help me?

There is given a whole number (that you need to insert by yourself using the command cin>>), and I need to determine is that number a prime or not. If it's a prime number I need to cout >> "1" and if it's not cout "0" , also it's mandatory to use the function:
bool IsPrime(long long a)

[adam2016]

just think to yourself, what is the definition of a prime?

A prime is a number that has two divisors - 1 and itself, so if a number has 3 divisors it is not a prime number.

An algorithm to solve this is pretty simple,

test a number: let's say 83, check if all numbers between 2-82 can divide evenly into 83(hint use the % operator to test for an even number), if so return false, if we finish the loop and we have not returned false, we can return true

you don't actually have to test from 2- the Number, but rather 2 - square root of the number.

also post your attempt if you need further help.

[deleted account xyzzy]

To determine if a number (greater than 1) is prime or not you need to iterate and check from 2 to n / 2. Any iteration above n / 2 is redundant.

[seeplus]

There's been previous threads on prime. Doing a search should find some info.

[jonnin]

most of the prime stuff in the forum are about finding them.
there are a number of primality tests that can tell you if something is prime to a very, very high percentage probability with FAR less work. If you are willing to risk the small % of wrong answers. They are good enough for most tasks. You can do a web search on primality tests if you want to see what you can find and whether you want to do it that way.

for small primes (tens of millions?) you can just make a lookup table.

[TheIdeasMan]

Furry Guy wrote:

To determine if a number (greater than 1) is prime or not you need to iterate and check from 2 to n / 2. Any iteration above n / 2 is redundant.

The limit should be the square root of the number, which is much smaller than n/2.

[neonblue00700]

Hello so I did this :

#include <iostream>
using namespace std;

bool IsPrime(long long a);

int main()
{

long long a;
cin>>a;
if(IsPrime(a))
cout<<1;
else
cout<<0;
}
bool IsPrime(long long a){
bool Pirminis = 1;
if (a==0 || a==1){
bool Pirminis = 0;
}
else
{
for (int i=2;i<=a/2;i++)
{
if (a % i == 0)
{
Pirminis = false;

}
}
}
return Pirminis;
}

[neonblue00700]

But there is some problems with it . When I try to insert number like 1000019597 or 1000004249 it doesn't give me an answer. And when I write in 1 for some reason the answer given is 1 and not 0.

[seeplus]

#include <iostream>
#include <cmath>
using namespace std;

bool IsPrime(unsigned long long a);

int main()
{
	/*
	for (unsigned long long a = 1; a < 1000; ++a)
		if (IsPrime(a))
			cout << a << " ";
	*/

	unsigned long long a {};

	cin >> a;

	cout << boolalpha << IsPrime(a) << '\n';
}

bool IsPrime(unsigned long long a) {
	bool Pirminis {a == 2 || (a > 2 && (a % 2))};

	for (unsigned long long i = 3, j = sqrt(a); Pirminis && i <= j; i += 2)
		Pirminis = (a % i);

	return Pirminis;
}

1000004249
true

[againtry]

#include <iostream>

using namespace std;

bool IsPrime(long long);

int main()
{
    
    long long a;
    cin >> a;
    
    if(IsPrime(a) == true)
        cout << "TRUE";
    else
        cout << "FALSE";
    
    cout << endl;
}

bool IsPrime(long long a)
{
    bool Pirminis = true;
    
    if (a == 0 || a == 1)
    {
        return false;
    }
    else
    {
        for (int i = 2; i * i <= a; i++) // <--
        {
            if (a % i == 0)
            {
                return false;
            }
        }
    }
    
    return Pirminis;
}

[seeplus]

Even numbers are not prime (except for 2). So there's no need to start at 2 and inc by 1. First deal with 0, 1, 2 and then test if is even. The loop then starts at 3 and incs by 2 if odd.

[againtry]

for (int i = 3; i * i <= a; i+=2) // <--