### Help with Printing Square Free Numbers

Hi there,

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"

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687`` ``````#include #include using namespace std; bool noSquare (int num); //Function to determine if the number is square-free vector 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 { return true; } vector Primes = getPrimes(num); //make a vector of all primes below the number being checked for (unsigned int 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 (unsigned int 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) { return true; } } } } return false; } vector getPrimes (int number) //Function to get a vector of all primes below num { vector 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 }``````
Last edited on
I fixed it! I replaced the bolded bit with
 ``123456789101112131415`` ``````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 { return true; //If it is, that means the number is square-free so return true } } else if (num%Primes[j] == 0) //If the current number divided by Primes[j] has a remainder, it cannot be square-free { return false; //Return that it is not square free } } return false; //Assume non-square-free until told otherwise ``````

and now it works :D
Topic archived. No new replies allowed.