I'm currently trying to write a program that takes an integer input from the user and displays that number of square-free numbers. I've gotten most of the program to work, but I encounter an error during the noSquare function that causes it to print incorrectly. I have bolded the area where I believe the problem is and I was hoping someone could help me figure out what I am doing wrong.
Thank you,
Tristan
P.S. A square-free number is a number that is not evenly divisible by the square of any prime number, in case anyone was unsure :)
EDIT: It's hard to see the bold in the code area, but it begins after the "//I think below is where the problem is"
#include <iostream>
#include <vector>
usingnamespace std;
bool noSquare (int num); //Function to determine if the number is square-free
vector<int> getPrimes(int num); //Function to get a vector of all primes below num
bool isPrime (int number); //Function to determine if individual numbers are prime
int main()
{
int num;
cout << "Please enter a number." << endl;
cin >> num; //Get input
cout << "The first " << num << " square-free numbers are:" << endl;
int total = 0; //Tracker for number of square-free numbers printed
int i = 1; //Number to use in loop through
while (total < num) //Keep looping until the right number of square-frees were printed
{
if(noSquare(i)) //Check if i is square-free
{
cout << i << endl; //Print out i
total++; //Update total
}
i++; //Update number after going through loop
}
return 0;
}
bool noSquare (int num) //Function to determine if the number is square-free
{
if(num == 1) //1 screws things up, so make a special case for it
{
returntrue;
}
vector<int> Primes = getPrimes(num); //make a vector of all primes below the number being checked
for (unsignedint j = 0; j < Primes.size(); j++) //Square all the primes in the vector
{
Primes[j] = Primes[j]*Primes[j];
}
//I think below is where the problem is
for (unsignedint j = 0; j < Primes.size(); j++) //Loop through all ints in the Primes vector
{
for (int k = 1; k < num; k++) //Loop through all numbers below the number being checked
{
if (num/Primes[j] != k)
{
if (j == Primes.size()-1 && k == num - 1)
{
returntrue;
}
}
}
}
returnfalse;
}
vector<int> getPrimes (int number) //Function to get a vector of all primes below num
{
vector<int> nums; //Create a vector to store primes in
for (int i = 2; i <= number; i++) //Loop through all numbers from 2 to the number being checked
{
if (isPrime(i)) //Determine if i is prime
{
nums.push_back(i); //If it is, enter it into the vector
}
}
return nums; //Return the vector full of primes
}
bool isPrime (int number) //Function to determine if individual numbers are prime
{
bool Prime = true; //Assume it is prime until told otherwise
int maxIndex = number/2;
for (int index = 2; index <= maxIndex; index++)
{
if (number%index == 0) //If there is no remainder then the number is composite
{
Prime = false;
break;
}
}
return Prime; //Return the bool value of Prime
}
for (int j = 0; j < Primes.size(); j++) //Loop through all numbers in the Primes vector
{
if(num%Primes[j] != 0) //If the current number divided by Primes[j] has no remainder, it could be square-free
{
if (j == Primes.size()-1) //Check if the current number is the last number in Primes
{
returntrue; //If it is, that means the number is square-free so return true
}
}
elseif (num%Primes[j] == 0) //If the current number divided by Primes[j] has a remainder, it cannot be square-free
{
returnfalse; //Return that it is not square free
}
}
returnfalse; //Assume non-square-free until told otherwise