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]