We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Fundamentals
  4. Leonardo's Prime Factors
  5. Discussions

Leonardo's Prime Factors

  • tarasyaremabcn
     + 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;
}