## Posts Tagged ‘divisor

19
May
09

### [C++] Numbers with 6 divisors where none of the divisors are primes > 5

My uncle phoned me up to day with a question:

N is a number that has exactly 6 factors.
One of the factors is 1, and another is the number itself.
None of the prime factors of N can be greater than 5
Find a method for calculating a set of vales that would suit N.

Well. To be honest, after literally hours of trying to work out how to do this, I gave up and decided to program a brute force algorithm that would do this for me:

```#include "stdafx.h"
#include "math.h"

int main()
{
//Algorithm to calculate numbers where
//Number of divisors < 7
//None of the prime divisors > 5
for(int i=1;i<100;i++) {
int dc = 0; //divisor count
bool pc = true; //prime check
for(int k=1;k<(i/2)+1;k++) { //loop through all the numbers up to (n/2)+1
if(i%k==0) { //check to see if divides with no remainder
dc++; //increase divisor count
if(dc > 5) { //if divisor count greater than 5, then quit - this number is not valid
dc++;
break;
} else { //else we need to check the divisor
if(k>5) {//if the divisor is bigger than 5, we need to check if it is prime
bool ip = true; //is prime?
for(int j = 2; j <= sqrt((double)k); j++)  //loop through the possible values
if(k % j == 0) //check remainder
ip=false;
if(ip==true) { //sorry, its too big to be prime. quit
pc=false;
break;
}
}
}
}
}
if(dc==5 && pc==true) //check number is prime valid and has 6 divisors
printf("Valid Number %d, \n", i);
}
return 0;
}```

That would produce the list of valid numbers, those being:
12 : [1, 2, 3, 4, 6, 12]
18 : [1, 2, 3, 6, 9, 18]
20 : [1, 2, 4, 5, 10, 20]
32 : [1, 2, 4, 8, 16, 32]
45 : [1, 3, 5, 9, 15, 45]
50 : [1, 2, 5, 10, 25, 50]
75 : [1, 3, 5, 15, 25, 75]