# Leonardo's Prime Factors

# Leonardo's Prime Factors

+ 17 comments Here's my solution (in C), which doesn't use a list of primes.

#include <stdio.h> #include <stdlib.h> unsigned long long int gcd(unsigned long long int a, unsigned long long int b) { while (b) { unsigned long long int t = b; b = a % b; a = t; } return a; } unsigned int max_unique_primes(unsigned long long int n) { unsigned int count; unsigned long long int prod; unsigned long long int prim; if (n < 2) return 0; prod = 2; count = 1; for (prim = 3; prod * prim <= n; prim += 2) { if (gcd(prod, prim) == 1) { prod *= prim; count++; } } return count; } int main(void) { unsigned int q; if (scanf("%u", &q) != 1) return EXIT_FAILURE; while (q--) { unsigned long long int n; if (scanf("%llu", &n) != 1) return EXIT_FAILURE; printf("%u\n", max_unique_primes(n)); } return EXIT_SUCCESS; }

+ 2 comments The problem writer should not have used "unique" primes in their verbiage. "Unique primes" are a different type of prime altogether.

+ 11 comments Here is my pretty simple and fast algorithm that can solve this problem for up to 1 < n < +2^63-1 with unsigned long long int variables.

For the max possible n (in C) we have that n = +2^63-1 = 9223372036854775807. The answer is 15, so we only need the first 16 prime numbers in the primes array (pr[16]).

#include <stdio.h> #include <stdlib.h> int pr[16] ={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53}; /* Function that returns the maximum number of unique prime factors for any number in the inclusive range [1,n] */ int factors (unsigned long long int n) { unsigned long long int x = 1; int i = 0; while ( x <= n && i < 16 ) { x = x * pr[i]; /* Some debug tests (can help you understand this function) int j; printf("%d: %d", i, pr[0]); for (j = 1; j <= i; ++j) { printf(" * %d", pr[j]); } printf(" = %lld <? %lld\n", x, n); */ ++i; } return i - 1; } int main() { int t, i; /* Really important to use at least a usigned long long int variable, if not there will be overflow */ unsigned long long int n; scanf("%d", &t); for (i = 1; i <=t; ++i) { scanf("%lld", &n); printf("%d\n", factors(n)); } return 0; }

+ 0 comments Instead of defining an array of primes, define an array of primorials to avoid calculating products. A Primorial is a product of the first n primes. Then simply perform an equality test in a loop and output the index of the array. Keep in mind that 16th primorial is larger than 2^64 so when defining your array, simply reduce the 16th primorial to fit into 2^64, but keep it larger than 10^18 limit specified by the question.

+ 7 comments If you use Java, you need BigInteger to store multiplied values, if you don't use you cannot pass TC 11,16 and 17.

Sort 291 Discussions, By:

Please Login in order to post a comment