hasKSmallFactors() not giving desired output

[CollinsLainzo]

Hello guys,

I am working on a problem where I am supposed to write a function hasKSmallFactors with signature boolean hasKSmallFactors(int k, int n) which returns true if n has k-small factors. The function should return false if either k or n is not positive.

So, given a positive integer k, another positive integer n is said to have k-small factors if n can be written as a product of u*v where u and v are both less than k.

E.g 20 has 10-small factors since both 4 and 5 are less than 10 and 4*5=20 (For the same reason, it is also true to say that 20 has 6-small factors, 7-small factors, 8-small factors, etc. However, 22 does not have 10-small factors since the only way to factor 22 is as 22 = 2 * 11, and 11 is not less than 10.

 
#include <iostream>
using namespace std;
bool hasKSmallFactors(int k,int n);
int main()
{
	int x,y;
	cout<<"Enter Ksmall Factor";
	cin>> x;
	cout<<"Enter number:"<<endl;
	cin>>y;
	if(!hasKSmallFactors(x,y))
	{
		return false;
	}
	return true;
																		
}
bool hasKSmallFactors(int k,int n)
{
	bool hasKSF=true;
	int u,v;
	if((u>=k)||(v>=k))
	{
		return false;
	}
	n=u*v;
	if((n%u!=0)||(n%v!=0))
	{
		return false;
	}
	return hasKSF;
}

The problem is my code runs successfully but doesn't give desires output.

I need some support with this please.

[salem c]

$ g++ -Wall -Wextra foo.cpp
foo.cpp: In function ‘bool hasKSmallFactors(int, int)’:
foo.cpp:22:2: warning: ‘u’ is used uninitialized in this function [-Wuninitialized]
  if((u>=k)||(v>=k))
  ^
foo.cpp:22:11: warning: ‘v’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  if((u>=k)||(v>=k))
           ^

Your initial comparisons are with junk data.

Also, main doesn't return a boolean 'false' or 'true'.
https://en.cppreference.com/w/cpp/utility/program/EXIT_status

[CollinsLainzo]

Ok so rather than the whole criticism can I get at least an algorithm on how I'm going to solve the problem

[jonnin]

how big is your problem going to be?
The easy way to do this is to make an array of the first however many prime numbers, whatever you want to support. If it gets to be too large, you will need a better algorithm, but for 'small' values this is going to work great. (For reference I have used an array of the first 1 million primes for stuff like this, you can do much more than a million, but its a nice round number for when to swap to a better approach).
so now you have an array with 2,3,5,7,11,13,17,... the prime numbers.
then just iterate and count … for each prime, divide it into your number so long as the remainder is zero. As soon as the remainder is not zero, you can't divide by that value anymore, try the next prime. Continue until the number you have left is prime or you have counted enough factors to be true.

example. 100:
100 /2 is 50, +1 factor
50/2 is 25, +1 factor
25/2 fail,
25/3 fail
25/5 is 5 +1 factor.
5 is in your list, its prime, +1 factor, stop.

[JLBorges]

#include <cmath>

// return true if n can be written as a product of u*v,
// where u and v are both less than k.
bool hasKSmallFactors( int k,int n ) {

    // return false if either k or n is not positive.
    if( k < 1 || n < 1 ) return false ;

    // both u and v can't both be less than the square root of n
    if( k < std::sqrt(n) ) return false ;

    // brute force
    // without loss of generality, assume that u <= v
    for( int u = 2 ; u < k ; ++u )
        for( int v = u ; v < k ; ++v )
           if( u*v == n ) return true ;
           // note: can break out of the inner loop if u*v > n

    return false ;
}

[jonnin]

is this the same?

for( int u = 2 ; u < k ; ++u )
{
      v = (n/u)%k; //replace v for loop with only possible value, if I did that right?
    if(..etc
}

[CollinsLainzo]

Thanks for the contributions guys. @JLborges I have tried your function but it keeps returning false for all tests. It never evaluates to true i.e given k= 10 and n=20 it returns false. I have tried to tweak the logic to no avail @jonin I won't be able to say for sure with your snippet.

However, I was able to get a solution which works to an extent...

bool hasKSmallFactors(int k, int n)
{
    bool result = false;
    int u = 1, v = 1;
    for (int i = 2; i < n/2; i++)
    {
      	if (n % i == 0)
        {
            u = v;
            v = i;
            if (u * v == n)
            {
                if (u < k && v < k)
                {
                    result = true;
                   	break;
				}
				
            }
        }
    }
    return result;
}

The problem with this function is, if n is a perfect square it keeps returning false for values that are suppose to be k-small factors of the perfect square n.
I have tried adding an if statements that should allow the function return true where u==v still won't work.
Would like someone to help out with this existing code and offer a bit of explanation if possible.
Thanks as always guys.

[JLBorges]

> I have tried your function but it keeps returning false for all tests.
> It never evaluates to true i.e given k= 10 and n=20 it returns false.

I'm unable to reproduce that behaviour. For instance, it does return true for k == 10 and n == 20

With some debugging scaffold added,

#include <iostream>
#include <cmath>

// return true if n can be written as a product of u*v,
// where u and v are both less than k.
bool hasKSmallFactors( int k,int n ) {

    // return false if either k or n is not positive.
    if( k < 1 || n < 1 ) return false ;

    // both u and v can't both be less than the square root of n
    if( k < std::sqrt(n) ) return false ;

    // brute force
    // without loss of generality, assume that u <= v
    for( int u = 2 ; u < k ; ++u )
        for( int v = u ; v < k ; ++v )
           if( u*v == n )
           {
               #ifndef NDEBUG
                   std::cout << " => " << u << " * " << v << " == " << n ;
               #endif // NDEBUG
               return true ;
           }

    return false ;
}

void test_it( int k, int n )
{
     std::cout << "k == " << k << "  n == " << n ;
     const bool result = hasKSmallFactors( k, n ) ;
     std::cout << "  hasKSmallFactors(k,n) == " << std::boolalpha << result << '\n' ;
}

int main()
{
    test_it( 10, 20 ) ;
    test_it( 10, 22 ) ;
    test_it( 6, 20 ) ;
    test_it( 6, 25 ) ;
    test_it( 6, 36 ) ;
    test_it( 12, 77 ) ;
    test_it( 11, 77 ) ;
}

http://coliru.stacked-crooked.com/a/5ecf9f4cc9b37ddf

[CollinsLainzo]

Thanks! great stuff... too much coding though.

This mesmerized me though:

bool hasKSmallFactors(int k, int n) 
{
	for(int u=k;u>=2;u--) //counting from k down to 2
	{
		int r=n%u;		//divide n by u store the remainder in r
		int v=n/u;		//divide n by u store the quotient in v (v and u are factors of n)
		if(r==0 && v<k && u<k)  // if there is no remainder and v being a factor is less than k 
		{						//and u being another factor is also less than k, then return true
			return true;
		}
	}
	return false;			//return false after iterating from k down to 2 and conditions are not met
}

and it worked perfectly with so little coding.
Great stuff! Thanks once again for all your contributions.

[jonnin]

that is about the same logic/idea as what I was replacing the second for loop with.
mine says v = n/u as above, and then takes the remainder off k.
what that did is allow for the if statement that followed to work.
if v*u = n, then it divided evenly (everything is an integer, so v*u would not == n if they did not). the remainder returns one of two things... either its n/u or its a number less than k. so if n/u gives a value bigger than k, the remainder part changes n/u to be incorrect so that v*u is no longer n.


an example... 100 and 5... try 2. 2 is a factor. 100/2 is 50. 50%5 is 0. 2*0 is not 100. false!

another example. 10 and 7. 10 /2 is 5. 5%7 is 5. 2*5 is 10. true.

one of the most used parts of 'remainder theory' from math is that the remainder can be between 0 and n-1. that is, %5 can give 0,1,2,3,4 and nothing else for any number x in x%5. here it is x % k, so if the number is out of bounds, it gets changed to one of many invalid values that won't give true when tested back (u*v == n will be false). Its not even 'coding' so much as 'fun with math'