CODEWITHSUNDEEP
c++algorithm
StormsEdge
StormsEdge

Reputation: 885

Print divisors in order using theta(n) efficiency

I'm struggling to implement this correctly. I want to create a function that determines all of the divisors of the user input userNum and outputs them to the user. When userNum = 16 i'm getting the output 1 16 2 8. I didn't expect the order to be correct, but i'm missing 4 and am struggling to figure out why. Any thoughts? I'm trying to do this in theta(sqrt(num)) efficiency.

void PrintDivisors(int num);

int main()
{
    int userNum;

    //Request user number

    cout << "Please input a positive integer >=2:" << endl;
    cin >> userNum;

    PrintDivisors(userNum);

    return 0;
}

void PrintDivisors(int num)
{
    int divisorCounter;

    for (divisorCounter = 1; divisorCounter < sqrt(num); divisorCounter++)
    {
        if (num % divisorCounter == 0 && num / divisorCounter != divisorCounter)
            cout << divisorCounter << endl << num / divisorCounter << endl;
        else if (num % divisorCounter == 0 && num / divisorCounter == divisorCounter)
            cout << divisorCounter << endl;
    }
}

Update: I have all the numbers printing, but still trying to determine how to print them in order while remaining within theta sqrt(n) efficiency

Upvotes: 1

Views: 682

Answers (4)

imbatman
imbatman

Reputation: 518

This is the solution I ended up using, which saves space complexity too. I was struggling to think of effective ways to loop over the solution in ascending order, but this one runs very fast and is nicer than appending to a vector or array or some weird string concatenation.

void printDivisors(int num)
{
  for (int k = 1; k*k < num; k++)
  {
      if (num % k == 0)
          cout << k << " ";
  }

  for (int d = sqrt(num); d >= 1; d--)
  {
      if (num % d == 0)
          cout << num / d << " ";
  }

  cout << endl;
}

Upvotes: 0

Ayon Nahiyan
Ayon Nahiyan

Reputation: 2200

For making it run in sqrt(n) time complexity:

For any n = a X b. either a<=sqrt(n) or b<=sqrt(n). So if you can find all divisors in range [1,sqrt(n)] you can find other divisors greater than sqrt(n)

You can use a for loop to traverse numbers in range 1 to sqrt(n) and find all the divisors less than sqrt(n), which at the same time you can also use to find other numbers greater than(or equal to) sqrt(n).

Suppose a number i < sqrt(n) is divisor or n. In that case the number k = n/i will also be divisor of n. But bigger than sqrt(n).

For printing numbers in sorted order:

During finding divisors in range [1,sqrt(n)] print only divisor in range [1,sqrt(n)] You can use an array/vector to store numbers in range [sqrt(n),n] and print them after the for loop ends. Here is a sample code

vector<int> otherNums;
for(i=1;i*i<n;i++) {
    if(num%i==0){
        cout<<i<<endl;
        otherNums.push_back(n/i);
    } 
}
if(i*i == n) otherNums.push_back(i);
for(i=(int)v.size() - 1 ;i>=0;i--) 
    cout<<otherNums[i]<<endl;

Upvotes: 0

Ivan Gritsenko
Ivan Gritsenko

Reputation: 4236

  1. Change loop termination condition operation to <=, now you will observe 4.

  2. Get rid of sqrt function call. Better use this loop

    for (divisorCounter = 1; divisorCounter * divisorCounter <= num; divisorCounter++)

Upvotes: 2

sudo make install
sudo make install

Reputation: 5669

Make sure to check your edge conditions carefully.

  1. What is sqrt(num)?
  2. What is the largest divisorCounter that will pass the test in the for loop?
  3. Would 4 pass the test?

I think if you look carefully at that line with these three questions in mind you will squash the bug.

Upvotes: 0

Related Questions