prime

[darkovasic014]

#include <iostream>
#include <cmath>
using namespace std;
// Function must be declared before being used.
bool prime(int n);
int main() {
int i;
// Set up an infinite loop; break if user enters 0.
// Otherwise, evaluate n from prime-ness.
while (true) {
cout << "Enter num (0 = exit) and press ENTER: ";
cin >> i;
if (i == 0) // If user entered 0, EXIT
break;
if (prime(i)) // Call prime(i)
cout << i << " is prime" << endl;
else
cout << i << " is not prime" << endl;
}
system("PAUSE");
return 0;
}
// Prime-number function. Test divisors from
// 2 to sqrt of n. Return false if a divisor
// found; otherwise, return true.
bool prime(int n) {
int i;
for (i = 2; i <= sqrt(n); i++) {
if (n % i == 0) // If i divides n evenly,
return false; // n is not prime.
}
return true; // If no divisor found, n is prime.
}
Write a program that finds the first prime number greater than 1 billion

Help please,I really don't know how to do this.

[Stewbond]

Okay, you have two issues:

First, there is no standard int sqrt(int n) function. You will either have to write a version of this function:

int sqrt(int n)
{
    for (int i = 1; i< n; i++)
        if (i*i > n) return i;
}

or cast n as a double:
for (i = 2; i <= sqrt((double)n); i++) {

Second:
You get your user to manually enter an input. You program then tells the user if the number is prime. This is fine, except that user will need to manually enter 1 billion and then adding 1 to his guess each time until he gets a prime number. You will want to automate this:

Instead of asking the user to enter a number, just set i=1000000. Increment i by 1 at the end of the while loop, and don't cout anything if the number is not prime or we will get a seriously huge number of messages. If the number is prime, output that number and then break from the while loop.

[georgep]

@Stewbond

You can definitely use sqrt so long as you are using the header <cmath>.

@darkovasic014

This is a simple function for finding whether a number is prime:

bool prime(int n){
 int a = 1;
   while(a <= sqrt(n)){
      a += 1;
      if(n % a == 0){
         return false;
      }
   }
 return true;
}

Below is a full program that will find the first prime greater than 1 billion. If you would rather work it out for yourself, stop reading now!

#include<iostream>
#include<cmath>

using namespace std;

bool prime(int n){ //function to find if n is prime
 int a = 1;
   while(a <= sqrt(n)){
      a += 1;
      if(n % a == 0){
         return false;
      }
   }
 return true;
}

int main(){
  
int n = 1000000000; //n starts at 1 billion

  while(1){ //loop that only breaks if n is prime
    if(prime(n)){ 
      cout << n << endl; //first prime over 1 billion
      cin.get();
      return 0;
    }
    else{
      n += 1; //if 1 billion is not prime, check 1,000,000,001 etc.
    }
  }
return 0;
}

[z05DSL3A]

georgep wrote:

You can definitely use sqrt so long as you are using the header <cmath>.

sqrt() with an integral argument has only been available (in the std library) since C++11, you may find that you need to do some type conversion if your compiler doesn't support it yet.

[georgep]

Thanks, I didn't know that. Never come across the problem myself.

[z05DSL3A]

georgeps code with a few mods to make it run faster.

//function to find if n is prime
bool prime(int n)
{ 
    if (n <=1)
        return false;
    else if (n == 2)         
        return true;
    else if (n % 2 == 0)
        return false;
    else
    {
        int a = 1;
        int upperLimit = sqrt(n);

        while(a <= upperLimit)
        {
          if(n % a == 0)
             return false;
          a += 2;
        }
    }
    return true;
}