Generating a set amount of prime numbers (C++)

[toobladink]

Well, back to school. I'm having issue with an assignment. Asked my TA earlier today and she wasn't able to help narrow down my issue. Would ask my professor, but he hasn't responded to my email and his office hours are packed with kids coming to him to get credit for properly setting up their VM. In other words, literally impossible to get help from him.

 

I feel like my approach is decent, given the parameters. We need to have a function that checks if a number is a prime and return it as a bool. We also need to just generate a set amount of prime numbers.

 

My current issue is that I can put in the amount of numbers I want to display, and it displays 2 and 3, but then displays -2147483647, and then -2147483646, etc until it's displayed the amount of numbers I want.

 

My approach is to take a variable and start from 1. I then increment that variable, and check if it is a prime. If it is a prime number, it will print out. This variable gets incremented until the amount of prime numbers I want is generated. Hopefully that's somewhat clear in my code.

 

Here is the part of my code I am concerned about:

void getInfo(int&, int&);
bool is_prime(int);
int calcPrime(int);

int main() {
 int P; // the amount of prime numbers to be found (he wants it to be called P)
 int totalNum = calcPrime(P);
 cout << "Total prime numbers: " << totalNum << endl;

 return 0;
}

bool is_prime(int num) {
 int i;
 bool isPrime = true;
 for (i = 1; i < num/2; i++)
 {
  if ((num % i) == 0) {
   return isPrime = false;
   break;
  }
  else {
   return isPrime = true;
  }
 }
}
int calcPrime(int P){
 bool checkPrime = false;
 int i = 0;
 int totalPrimeNum = 0;
 while (totalPrimeNum < P) {
  i++;
  checkPrime = is_prime(i);
  if (checkPrime) {
   totalPrimeNum++;
   cout << i;
  }
 }
}

 

[mariushm]

Double check your  is_prime function, it looks wrong to me.

 

Think using "return" only once in that function.

 

 

 

 

[xentropa]

in the GMP library there is a built in function called nextprime.  If you input a number, it will output the next prime number.

 

you could use a for loop

[esevre]

There is definitely a problem in the is_prime() function.

 

Let me give you a couple hints:

What is n%1 for all integers?

I often try to increase my performance by checking if n == 2, then if n is divisible by 2.

Once that check is done then you only need to test odd numbers (so start with i = 3, and i+=3).

 

I hope this helps.

[wanderingfool2]

//As a note, almost always in math, 1 is not considered prime, so you should treat it accordingly
bool is_prime(int num) {
 int i;
 bool isPrime = true;
 //When num <= 2 your loop never runs, which is why you get negative numbers as primes and the first 2 correct
 //You should run a check for num < 0
 for (i = 1; i < num/2; i++)
 {
  if ((num % i) == 0) { //num%1 = 0 every time num is positive, so it will always return false
   //cerr << "num:" << num << " i:" << i; When debugging issues, if you don't have an IDE with an debug then start putting in cerr's where
   //where there may be potential issues...you will then be able to think about why something is failing
   return isPrime = false;
   break;
  }
  else {
   //cerr << "num:" << num << " i:" << i; Once you fix the above, you will notice another issue with your prime calculator...
   //Mainly you will get all odd numbers.
   return isPrime = true;
  }
 }
 //RETURN statement please, always have a return statement on code paths that can be reached when returning variables.  Otherwise you just get the default stuff (or in some stricter standards errors)
}

Added comments

[straight_stewie]

10 hours ago, toobladink said:

We need to have a function that checks if a number is a prime and return it as a bool. We also need to just generate a set amount of prime numbers.

Since your teacher will ask for a set amount of prime numbers you should consider looking into a Sieve of Eratosthenes. It is significantly faster, and in my experience easier to implement and less error prone. An upper bound for the value of the nth prime number (but probably not the nth prime number) is P_n < n(ln n + ln ln n). So that will give you the size of the sieve you will need to generate the nth prime.

To check if a given number is prime using a prime sieve, you can sieve up to sqrt(n) + 1. It is guaranteed that all non prime numbers have at least one factor below the square root of the number plus one (actually, it is guaranteed that they all have a factor below the square root, but when you go to implement this you will find that adding one to it makes things a little easier).

 

10 hours ago, toobladink said:

Here is the part of my code I am concerned about:

There is a big problem in your is_prime function. n%1 == 0 is true for all n.

[Unimportant]

The code as presented also never initializes P before passing it to calcPrime.

[toobladink]

2 hours ago, Unimportant said:

The code as presented also never initializes P before passing it to calcPrime.

P is initialized by prompting the user to enter a value from the console. There's a function that grabs it, sorta like a menu, that I took out of the code because it isn't really too relevant to my problem

 

8 hours ago, esevre said:

There is definitely a problem in the is_prime() function.

 

Let me give you a couple hints:

What is n%1 for all integers?

I often try to increase my performance by checking if n == 2, then if n is divisible by 2.

Once that check is done then you only need to test odd numbers (so start with i = 3, and i+=3).

 

I hope this helps.

This was actually super helpful and solved my issue with the bigger numbers. I can still generate some prime numbers, but I have some numbers show up that are not prime, such as 4 and 9. So if I ask for 8 prime numbers, my output is currently 2, 3, 4, 5, 7, 9, 11, 13.

 

My is_prime function looks like this now: (sorry the format looks wanky)

bool is_prime(int num) {
	int i;
    bool isPrime = true;
    for (i = 3; i < num/2; i+=3) // I've tried changing the i < num/2 to stuff like i < num
    {
    	if ((num % i) == 0) {
        	isPrime = false;
            break;
        }
        else {
        	isPrime = true;
        }
    }
	return isPrime;
}

I understand why 4 is showing up, so I've been messing around with the condition in the for loop, but I am not getting the results I want when I change it around to something else.

 

Thank you everyone else for the suggestions. I'll be trying things out over the next couple hours and will post what I end up submitting!

[Unimportant]

@toobladink Something along these lines perhaps?

bool is_prime(int num) 
{
	if (num == 2)
	{
		return true;
	}

	if (num > 1 && num % 2)
	{
		for (int i = 3; i < num; i += 2)
		{
			if (!(num % i))
			{
				return false;
			}
		}
		return true;
	}
	else
	{
		return false;
	}
}	

 

[reniat]

3 hours ago, straight_stewie said:

Sieve of Eratosthenes

Just to make sure it's seen, this is definitely the route you'll want to be going. It's not only pretty easy to implement, it's a very well established way to generate primes.

[straight_stewie]

3 hours ago, toobladink said:

but I have some numbers show up that are not prime, such as 4 and 9. So if I ask for 8 prime numbers, my output is currently 2, 3, 4, 5, 7, 9, 11, 13. 

It's literally trial division guys.
 

The algorithm is as follows:

• For all numbers greater than or equal to 2 and below sqrt(n) + 1
• Divide n by the number.
• If n is divisible by any number, it is not prime.
• If n is not divisible by a number it is prime.

 

Ergo:

include <math.h>

bool isPrime(int num):
{
  for (int i = 2; i < ((int) math.sqrt((double) num)) + 1; i++)
  {
    if (num % i == 0)
    {
      return false;
    }
  }
  
  // we can only reach this line if num is prime
  return true;
}

 

A slight optimization to avoid two casts every iteration of the loop, which can add a significant penalty for large num:

include <math.h>

bool isPrime(int num)
{
  int stopCondition = (int)(math.sqrt((double) num)) + 1;
  
  for (int i = 2; i < stopCondition; i++)
  {
    if (num % i == 0)
    {
      return false;
    }
  }
  
  // we can only reach this line if num is prime
  return true;
}

 

Be warned that if you haven't learned about casting, header files, or std yet, your teacher may find it suspicious that you are casting and using a library module. This thread may show up on a Google search. If the above case holds true, I would recommend that you use the simpler stopCondition = (num / 2) + 1. The plus one is necessary as singed integer division returns the floor of (dividend / divisor) and what we really want here, especially for some small n < 10, is the ceiling of (num / 2).

[esevre]

If you want to avoid using the sqrt function, you can test i-squared

for (int i = 3; i*i < num; i += 2)
{
    // do stuff here
}

 

If I am expecting "large" numbers, I will create a short list of primes to check primality of smaller primes, then start the loop at a higher value.

bool is_prime(int n) {
    const std::vector<int> small_primes {2, 3, 5, 7, 11, 13, 17, 19, 23};
    // checking for small primes
    if (n < small_primes.back()*small_primes.back()) {
        for (const auto &p : small_primes) {
            if (n == p) {  // this loop can be replaced with std::any_of from STL <algorithms>
                return true;
            }
        }
        return false;
    }
    // checking for larger primes
    // Some extra math can optimize this loop a bit too
    for (int i = 25; i*i <= n; i+=2) {
        if (n%i == 0){
            return false;
        }
    }
    return true;
}

 

[wanderingfool2]

21 hours ago, reniat said:

Just to make sure it's seen, this is definitely the route you'll want to be going. It's not only pretty easy to implement, it's a very well established way to generate primes.

My thought is that it isn't good to start off with Sieve of Eratosthenes....mainly due to the fact that it does take a bit more understanding to implement (which in the case of people who are beginning adds more areas to fail at).  It may be easy to implement for people who are semi-familiar with programming and it may be a well established way, but sometimes in learning you need to get more basic to teach the concepts first.

 

 

@toobladink how did everything work out? (Or do you have the weekend to work on it some more).

A few comments on your code you posted

bool is_prime(int num) {
	int i;
    bool isPrime = true;
    
    //There really should be an if statement here eliminating non-primes 1 and under (e.g. -10 is a prime according to the logic)
    
    //Always consider the numbers around the boundaries in loops.  when n = 4 or 6 you have the following logic
    // i = 3; 3 < 4/2 ... 3 < 2 ... false ... so the loop will not run.  Since you don't check for divisible by 2, you get 4 and 6 as primes
    // i = 3; 3 < 6/2 ... 3 < 3 ... false
    for (i = 3; i < num/2; i+=3) //i+=3 is incorrect, i = 3, 6, 9, 12...etc in your code.  You should not be adding by 3.
    {
    	if ((num % i) == 0) { //You corrected your internal if statements a lot, now it is just getting rid of unneeded statements
        	isPrime = false;
            break; //isPrime = false; break; and then returning isPrime can be summed up in a single return statement here.
        }
        else {
        	isPrime = true; //This is unneeded, you set isPrime = true before your loop and you only set isPrime to false when it isn't a
            //prime...so that means if isPrime = false, you shouldn't be setting it to true.  The else statement is not needed then
        }
    }
	return isPrime;
}

 

[toobladink]

/*
Class: CPSC 122-02
Team Member 1:
Team Member 2: None
Submitted By: 
File Name: proj2.cpp
Program generates prime numbers and writes them to an output file
To Build: g++ proj2.cpp -o proj2
To Execute: ./proj2
*/

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void getInfo(int&, int&, string&);
void openOutputFile(string, ofstream&);
void writeToFile(ofstream&, vector<int>&, int);
void displayPrimeNums(vector<int>, int);
bool is_prime(int);
void generatePrimes(int, vector<int>&);

int main() {
 int P, N; // stores Prime numbers user wants and N columns to be displayed
 string fileName;
 ofstream outputFile;
 vector<int> primeNums; // stores generated prime numbers
 
 getInfo(P, N, fileName);
 generatePrimes(P, primeNums);
 openOutputFile(fileName, outputFile);
 writeToFile(outputFile, primeNums, N);
 displayPrimeNums(primeNums, N); 

 return 0;
}

/*
Gets the amount of prime numbers to be generated (P),
the amount of columns to be displayed over (N),
and the name of the file the prime numbers will be written to (one per line)
*/

void getInfo(int& P, int& N, string& fileName) {
 cout << "How many prime numbers do you want to generate?" << endl;
 cin >> P;
 cout << endl << "How many columns do you want them displayed over?" << endl;
 cin >> N;
 cout << endl << "What file do you wish to write to? (Ex: num.txt) " << endl;
 cin >> fileName;
}

/*
Checks if a number is prime by modding it. If a number
mod anything equals 0, that means it is divisible so the function
returns false.
*/

bool is_prime(int num) {
 int i;
 bool isPrime;
  for (i = 2; i < num; i++)
  {
   if ((num % i) == 0) { 
    isPrime = false;
    break;
   }
   else {
    isPrime = true;
   }
  }
 return isPrime;
}

/*
This function generates an integer and then checks if it is prime.
If it is prime, it gets appended to the end of a vector.
*/

void generatePrimes(int P, vector<int>& primeNum){
 bool checkPrime = false;
 int i = 1; 
 int totalPrimeNum = 0; // keeps track of prime numbers that have been generated
 while (totalPrimeNum < P) {
  i++;
  checkPrime = is_prime(i);
  if (checkPrime == true) {
   primeNum.push_back(i); // puts the prime number at the end of the vector
   totalPrimeNum++; 
  }
 }
}

/*
This function opens the output file and makes sure it was opened.
If it was not opened, it closes the program.
*/

void openOutputFile(string fileName, ofstream& outputFile) {
 cout << "Attempting to open " << fileName << "..." << endl;
 outputFile.open(fileName);
 if (outputFile.is_open()) {
  cout << "Output file has been opened." << endl;
 }
 else {
  cout << "Output file not opened. Closing program." << endl;
  exit(-1);
 }
}

/*
This function takes the final vector and outputs the results
to the output file, also displays designated columns in output file
*/

void writeToFile(ofstream& outputFile, vector<int>& primeNum, int cols) {
 for (int i = 0; i < primeNum.size(); i++) {
  outputFile << primeNum.at(i) << '\t';
  if (i % cols == cols -1) {
   outputFile << endl;
  }
 }
 outputFile.close();
}

/*
Displays the prime numbers over the designated amount of columns in console
*/

void displayPrimeNums(vector<int> primeNum, int cols) {
 int i = 0;
 while (i < primeNum.size()) {
  cout << primeNum.at(i) << '\t';
  if (i % cols == cols - 1) {
   cout << endl;
  }
  i++;
 }
}

I uhh.. forgot to upload my final code here when I submitted the assignment, but here's what I ended up doing. Hopefully it's clear what's going on and what I decided to do. My professor reaelly emphasized that we have a function that checks if a number is prime, so I thought this way might be best. I'm sure he'll go over it and will be like "How many of you used Sieve of Eratosthenes?" but he seems like a very easy going guy and will show us a couple ways how we could have implemented that. The problem I saw with Sieve of Eratosthenes is there is no point to check if a number is prime if you know you generated a prime to begin with, and his emphasis on having a function that checks if a number is prime was the biggest factor in not me using it.

 

Anyways, thank you all very much for the help! My professor used his office hours this week to check each of his student's VMs to make sure they were set up the way he wanted and he didn't allow for questions, so I'm very thankful for all the help.