Finding Prime numbers

[Tej Samra]

Write a program that asks the user for a non-negative integer and then displays a message indicating if it is prime or not. A prime number is an integer that has no factors other than one and itself.

#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    int number;
   
   do{
   cout <<"Enter an integer:";
   cin>> number;

if((number%2==0) ||(number%3==0) || (number%4==0)||(number%5==0)||(number%6==0)|| (number%7==0)||(number%8==0)||(number%9==0))
    cout <<"number is not prime" << endl;
    
else 
    if((number/1==number) && (number/number==1))
    cout << "number is prime" << endl;

} while(number>0);
    cout << "Enter a positive Integer" << endl;
    system("PAUSE");
    return (0);
}

   

This is my code i have so far and I know why the number is not prime. lets take 5 as the number for example. 5%5=0 so the output will display number is not prime regardless of the second else if. This method isnt the best and doesnt work for integers less than 10. Any suggestions?

[firedraco]

Write down how you would figure out how a number is prime on paper first. Then try to turn it into code. Hint: Try using a loop of some kind with a % check inside it.

[Tej Samra]

algorithms and can you tell me the loop type?

[Volatile Pulse]

Personally, I'd use a for loop, something like:

for (int i = 2; i < number; i ++) {
   //enter your code to check if number is divisible by i
}

[Tej Samra]

Used the forloop but the output is continous due to the i++. Where is my mistake?

#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    int number;
   
  
   cout <<"Enter an integer:";
   cin>> number;
for(int i=2; i < number; i++)

 if (number%i==0)
 cout << "number is not prime" << endl;
 
 else
 if(number%i!=0)
  cout << "number is prime" << endl;
    
    system("PAUSE");
    return (0);
}

   

[Volatile Pulse]

the goal of the for loop is to test to see if the number is prime, keep your output on the outside of the for loop. Instead, declare a boolean at the beginning of main named something like isPrime = true and then inside of the for loop, if the number is divisible by i, set isPrime to false, then once the for loop is done, check to see if isPrime is true or false, and output accordingly.

[missione]

I got where the problem is. The "number%i" operation sometimes gets 0, but doesn't get 0 most of the time. Your program outputs for all % operation. The output should be after the loop is done. Also u need a boolean operation (true or false), to test the result of the loop after exiting the loop. I adjusted the program as follows. Try it, it works. I commented some of the lines I did not need from ur code.


#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
int number;
bool TEST;
TEST = true;

cout <<"Enter an integer:";
cin>> number;
for(int i=2; i < number; i++)

{
if (number%i==0)
TEST = false;
break;
//cout << "number is not prime" << endl;
}

if (TEST == false)
cout << number << " is not prime";
else cout << number << " is prime";
//else
// if(number%i!=0)
//cout << "number is prime" << endl;

//system("PAUSE");
// return (0);
}

[missione]

Hi, I also wrote another program that checks if a number is prime or not. Most programs use the % operator for testing. This one works without the % operator. It's less efficient, though. It can actually be made more efficient by using the "goto" statement instead of "break" inside the for loop. I hope u will like it.

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

int main(void)
{
int n,k,j,p;
bool TEST; // becomes false if a number is equal to multiplication of two other numbers
TEST = true; // initialize TEST


cout << "This is a prime number testing program" << "\n";
cout << "please input a number to test: ";
cin >> n;

for (j=2; j<n; j++) // multiply all numbers below n to see if it gives n

{
for (k=2; k<n; k++)

{
p=j*k;

if (p==n) // if a certain product equals n, TEST changes flag & loop is aborted
{
TEST = false;
break;
}

}

}

if (TEST == false)
cout << n << " is not prime";
else cout << n << " is prime";


}

[Volatile Pulse]

For your second example, what if you enter 4? Your program will say its prime. Your second for statement should be int j = 1; j < i; j ++

[missione]

To Volatile Pulse:

are you sure? I did compile it before posting and it says 4 is not prime. But you are right it will work even if you start the loop from j=1. I was trying to avoid getting 1*n=n, whose output would say all numbers are prime. But since the loop stops before n, it's safe.

[Shinigami]

Here is algorithm you need http://cplusplus.shinigami.lt/2012/04/05/prime-number-function/
you need only is_prime() funktion.

[Volatile Pulse]

@missione
I was wrong about the 4, your program would run it correctly, but your second for loop should still be changed to (int k = 1;k < j; k ++) so that the computer doesn't take as long to run, and per Shinigami's post, it is better to do for your first for statement (int j = 2; j <= (n / 2); j ++)

I didn't test it, but it should work just like your current one and also be much faster.

[Harry Potter]

you dont need to go checking till n, you only need to check till sqrt(n).
its a simple number theory concept. (if some factor is greater than sqrt(n), then there has to be a factor which is smaller than that. Both cannot be greater than sqrt(n). and if there are no factors till sqrt, then its a prime.)

This makes the code too fast. e.g. to check if 10001 is prime or not, you just need to check till 100. (you just saved 9900 worthless calculations! smart!)

Make sure you include math.h, to use sqrt function.

[Tej Samra]

thanks everyone for perfecting the code. The problem was that im learning from a textbook and I dont know functions like bool yet and am still understanding looping.

[Shinigami]

bool is not a function, it is a type like int or double. But bool can only be true (1) or false (0).

[Volatile Pulse]

That's a great idea potter, I think I'll use that in my project euler programs now. I appreciate the tip.

[Tej Samra]

To missione:
First code doesnt work not sure about second one

(number%i) also known as (number%2) because i=2 in the for loop will give wrong output sometimes. For example 9%2!=0 but it is not a prime since its divisible by 3. So the code is best and easiest when written like this.

#include<iostream>
#include <cstdlib>

using namespace std;

int main()

{
 
  int number;
 int count=0;
 
 cout<<"Enter an Integer:";
 cin>>number;
 
  for(int a=1;a<=number;a++)
  {
   if(number%a==0)
   {
    count++;
   }
}
  if(count==2)
    
   cout<<number << "is prime" << endl;
   
  else
   
   cout<<number <<" is not prime " << endl;
   
 system("PAUSE");
 return(0);
}

I cant believe i never thought of this..

[missione]

@ Tej Samara:

I like ur code, if count==2 when loop is finished it means it's prime (number is divisible only by itself & 1). Otherwise it's not prime. It's another way of using true or false boolean operation.

The reason my code did not work is I forgot to enclose the if clause with {}. Replace it as follows and it will work.

if (number%i==0)
{TEST = false;
break;}

9%2 !=0, but 9%3 will be 0 when i=3 and output will not be prime

To make ur program faster, u can make the loop to exit whenever count>2 and run the loop till sqrt(n) as suggested by potter.

[Tej Samra]

oh i see and thanks.

[Shinigami]

@ Tej Samara:
you do not need to check if(number%a==0) if a > (number / 2 + 1) it will newer be 0. So you count only to half a number and start only from 2 as 1 will always be 0;
for (int i = 2; i < (number / 2 + 1); i++)
and
if (number%i == 0)
it will be not a prime number.
so function looks like this

bool is_prime(const int & number)
{
    if (number < 2)
    {
            return false;
    }
    
    for (int i = 2; i < (number / 2 + 1); i++)
    {
        if (number%i == 0)
        {
            return false;
        }
    }
    return true;
}

you can change (number / 2 + 1) to sqrt(number+1) too.
for (int i = 2; i < sqrt(number+1); i++)