Prime Number Check

[aprendiz]

Hi, I am a newbie in c++ programming. I wrote a simple code to check if a number is prime or not. But code is not working correctly. It checks some numbers correctly and some numbers incorrectly. Can some one identify mistakes in my code?? please.

unsigned long a,b;
    cout<<"Enter a number: ";
    cin>>a;
    for (int i=2; i<a; i++)
    {
    b=a%i;
    if(b == 0)
              {
              cout<<"Not Prime!";
              cout<<endl;
              break;
              }
    else
    {
        cout<<"Prime."<<endl;
        break;
    }
    }
    return 0;

It shows 49 as a prime number.. :(

[UldisK]

if(b==0) means you have found an not prime number, but you incorrectly assume that if b!=0 (the else statement), that it is a prime.

[Chervil]

The problem is the loop terminates too soon. If b==0 the number is not prime, that is ok. But in order for it to be prime, the loop must continue checking all the other values of i.

    unsigned long a;

    cout<<"Enter a number: ";
    cin>>a;

    bool prime = true;

    for (int i=2; i<a; i++)
    {
        if (a%i == 0)
        {
            prime = false;
            break;
        }
    }

    if (prime)
        cout<<"Prime."<<endl;
    else
        cout<<"Not Prime!" <<endl;

[hunter86bg]

I will post my code for the Sieve of Eratosthenes algorithm. I got helped yesterday finishing it and it got quite clear and understandable.Just examine it and if you don't get the idea - don't worry it took me some time to get to the end.
Here is it:

/* Sieve of eratosthenes project for finding primes
up to 100 */

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int max=100;
    cout <<"Enter max number: \t";
    cin >> max;
    vector<bool> sequence(max,true);
    sequence[0]=false; 
    sequence[1]=false;

    for (int i=2; i<max;++i)
        if (sequence[i])
            for (int x=i+i; x<max; x+=i)
                sequence[x] = false;

    for (int z=0;z<max;++z)
        if (sequence[z])
            cout << "Prime number: " << z <<endl;

    return 0;
}

[usmiech]

Hi, I've just started C++ as well, my simple code for prime number is :


#include "stdafx.h"
#include <iostream>
#include <math.h>
using namespace std;

int main() {
int n = 0;
bool is_prime = true;

cout << "Enter a number and press ENTER: ";
cin >> n;

for (int i = 2; i <= sqrt(double(n)); i++) {
if (n % i == 0)
is_prime = false;
}

if (is_prime)
cout << "Number is prime." << endl;
else
cout << "Number is not prime." << endl;

system("PAUSE");

return 0;
}


code findes primes to all numbers...

[Chervil]

@usmiech Well done. The test for square root is a useful optimisation, it cuts down on unnecessary iterations of the loop.

Just one suggestion. As presented above, the sqrt() function is called on each iteration of the loop, which is detracting a bit from the advantage gained. So I'd suggest calling it just once before the loop begins:

    int limit = sqrt(double(n));
    for (int i = 2; i <= limit; i++) {

[aprendiz]

I got it. Thank you all. this forum is much better than my programming class.

[vlad from moscow]

I also decided to write a program that determines whether a number is prime.

#include <iostream>

int main()
{
	while ( true )
	{
		std::cout << "Enter a non-negative number (0 - exit): ";
		size_t x = 0;
		std::cin >> x;

		if ( !x ) break;

		bool prime = x == 2 || x % 2;

		for ( size_t i = 3; prime && i < x / 2; i += 2 )
		{
			prime = x % i != 0;
		}

		std::cout << x << " is " << ( prime ? "" : "not " ) 
		          << "a prime number\n" << std::endl;
	}

	return 0;
}

[usmiech]

Thx Chervil :)

[sujan]

#include<iostream.h>

int main()
{
int n;
int i;
int flag= 0;
cout<<"Enter the number";
cin>>n;
//cout<<endl<<n;
for(i=2;i<n;i++)
{
flag = n % i;
if(flag == 0)
{
cout<<"Not prime";
break;

}
flag++;


}
if(flag>0)
{
cout<<"Prime";

}


system("PAUSE");
cin.get();
return 0;


}

[usmiech]

Hi, my next try ...
Code for prime number... but ...
It returnes factors and a next prime.... Unfortunately just for not prime number... But I started learning C ++ 10 days ago....sorry :).... Every day I am getting better ;)



#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;
bool prime(int n);
void get_divisors (int n);
void next_prime (int n);



int main(){
int i;
while (true) {
cout << "Enter a num (0 = Exit) and press ENTER: ";
cin >> i;
if (i == 0)
break;
if (prime (i))
cout << "num is prime" << endl;
else
cout << "num is not prime" << endl;
get_divisors (i);
cout << endl;
next_prime (i);
cout << endl;
}
system ("PAUSE");
return 0;
}

bool (prime (int n)){
int i;
int limit = sqrt (double(n));
for (i = 2; i<= limit; i++){
if (n % i == 0)
return false;
}
return true;
}
void get_divisors (int n) {
int i;
int sqrt_of_n = sqrt (double(n));
for (i = 2; i <= sqrt_of_n; i++)
if (n % i == 0){
cout << i << ", ";
get_divisors (n / i);

return;
}
cout << n;
}
void next_prime (int n) {
int i;
int limit = sqrt (double(n));
for (i = 2; i <= limit; i++)
if (n % i == 0){
next_prime (n + 1);

return;
}

cout << "Next Prime: " << n;
}

[vlad from moscow]

This function

void next_prime (int n) {
int i;
int limit = sqrt (double(n));
for (i = 2; i <= limit; i++)
if (n % i == 0){
next_prime (n + 1);

return;
}

is invalid. First of all you should convert n to unsigned value otherwise the code will not work.

Also you are changing n but you are not changing the loop condition.

EDIT: Oh I am sorry. I did not see that you are using a recursion. Your function does return nothing. So its using has no any sense. I think that you should write it such a way that either it will return bool or the next prime number.

[usmiech]

As I said ... every day I'm getting better..... final code...:)



#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n);
void getDivisors (int n);
void getNextPrime (int n);

int MIN_PRIME = 2;

int main()
{
int userInput;


while (true)
{
cout << "Enter a num (0 = Exit) and press ENTER: ";
cin >> userInput;

if (userInput == 0)
break;
if (isPrime (userInput))

cout << "num is prime" << endl;
else
cout << "num is not prime" << endl;

getDivisors (userInput);
cout << endl;
userInput++;

getNextPrime (userInput);

cout << endl;
}

system ("PAUSE");
return 0;
}

bool isPrime (int i_numberToCheck)
{
int limit = sqrt (double(i_numberToCheck));

for (int i = MIN_PRIME; i<= limit; i++)
{
if (i_numberToCheck % i == 0)
return false;
}

return true;
}

void getDivisors (int i_numberToCheck)
{
int sqrt_of_n = sqrt (double(i_numberToCheck));

for (int i = MIN_PRIME; i <= sqrt_of_n; i++)
{
if (i_numberToCheck % i == 0)
{
cout << i << ", ";
getDivisors (i_numberToCheck / i);

return;
}
}
cout << i_numberToCheck;
}

void getNextPrime (int i_numberToCheck)
{
int limit = sqrt (double(i_numberToCheck));

for (int i = MIN_PRIME; i <= limit; i++)
{
if (i_numberToCheck % i == 0)
{
getNextPrime (++i_numberToCheck);

return;
}
}

cout << "Next Prime: " << i_numberToCheck;
}



ps
code checks: prime or not, gives all divisors /without 1/ , gives next prime..
compiler : Microsoft Visual Studio

[slamdon0709]

Hi ,i am also a new one who just begin c++. I just wrote a code for checking a number whether prime or not..check it out..


#include <cstdlib>
#include <iostream>
using namespace std;
int main()
{
int a,b,c,d;
cout<<"Type the number :";
cin>>a;
for(b=2;b<a;b++){
c=a%b;
if(c==0){
d=0;
break;
}
}
if(d==0){
cout<<a;
cout<<" is not a Prime Number"<<endl;
}
else{
cout<<a;
cout<<" is a Prime Number"<<endl;
}
system("PAUSE");
}
Thanks...

[vlad from moscow]

@slamdon0709

I'd like to ask is 2 a prime number?

[usmiech]

yes , it is.. just one even prime number..

[usmiech]

sorry slamdon, but it does not work.....