Help with Printing Square Free Numbers

[TWhytock]

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"

#include <iostream>
#include <vector>

using namespace 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
    {
        return true;
    }
    vector<int> 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<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
}

[TWhytock]

I fixed it! I replaced the bolded bit with

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