# Leonardo's Prime Factors

# Leonardo's Prime Factors

ian16 + 5 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; }

shibi1306 + 0 comments awesome logic.

- FH
fheil0815 + 0 comments this might not use a list of primes, but it is also much slower. calculating max primes runs in O(n*log(n)) (n for looking at all the numbers and log(n) for the gcd). using a list of primes is O(1) and you can make the list manually in a minute.

sgrebenkin + 0 comments Nice

- RP
ranjan_purbey + 2 comments Could you please explain how this works?

- TG
tpgreene + 0 comments https://en.wikipedia.org/wiki/Euclidean_algorithm

"The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. "

This is because said difference contains the gcd as well. This visualization helps some:

https://medium.com/i-math/why-does-the-euclidean-algorithm-work-aaf43bd3288e

Basically, any number larger than the smaller number would no longer be a factor for that number, so you can exclude it (and any multiple of it)

- TG
tpgreene + 0 comments If n<2, then it is 1 and has no primes. Otherwise, 2 is the smallest prime we start with ("count" of primes = 1). Prod is an ongoing multiple of the primes. As long as this number times the next possible prime (+2, only odd numbers greater than 2 are prime) is less then the original number, then we continue running the loop (the reason for this is similar to the explaination for euclidean algorithm given below).

Since the prod contains all of the previously obtained primes (multiplied together), then if the gcd == 1 (between prod and the "new" number), then that means that the "new" number is also prime, as none of the other primes (contained in prod) go into it. Therefore, we multiply it into our prod and continue onward, increasing the count. Once the for condition exceeds the original number, we have the full count and return that.

- TG
tpgreene + 0 comments [deleted]

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

iamSomanshu + 0 comments [deleted]- AY
Ankit_ISM_1997 + 0 comments Unique Solution

LINKONRUHUL + 0 comments [deleted]mitkonikov01 + 3 comments Here is my solution for better understanding :

int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}; int q; cin >> q; for (int i = 0; i < q; ++i) { unsigned long long current; cin >> current; if (current == 1) { cout << 0 << endl; continue; } unsigned long long temp = 1; int position = -1; int counter = -1; do { counter++; position++; temp *= p[position]; } while (temp <= current); cout << counter << endl; } return 0; }

- AP
alex_pn + 2 comments Curiously enough, when this code is executed an integer overflow occurs when

*temp*is multiplied by 53, but the code still produces correct result since 2*3*5*7*11*13*17*19*23*29*31*37*41*43*47*53-2^64 is greater than 10^18. Funny things start to happen when N is greater or equal to 14142414403480493114, but this value is outside of the range of allowed inputs.tarasyaremabcn + 0 comments Yeah, you can allways can go for a python solution or a bigint implementation on the C code. Nice that you noticed it!

einsteinFan + 0 comments upto 47 is enough

- SJ
jainsajal1301 + 0 comments Not valid when n is itself prime..

- KB
bak_karolek + 0 comments You can always divide n and check if it is > 0 istead of multiplying temp. There is no risk of overflow then.

bennattj + 0 comments Easier to just hard code the intervals (which is what I did). Then loop until your number is smaller than the next interval (this ith interval is the number of primes).

sgrebenkin + 0 comments The same approach, just lazy calculation with long overflow check.

- AF
afando + 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.

moguz00 + 4 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.

- AG
agollapudi2019 + 0 comments You can also check if your product has become negative so soemthing like if((product0)) it worked for me; but product has to be a long

KeyurPotdar + 2 comments I passed all the TC's just by using long

Scanner in = new Scanner(System.in); int q = in.nextInt(); int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}; while (q-- > 0) { long n = in.nextLong(); int count = 0; long product = 1; for (int i : prime) { product *= i; if (product <= n) { count++; } } System.out.println(count); }

- V
vaibhav_6451956 + 1 comment why you stopped taking primes beyond 47?

KeyurPotdar + 0 comments Because after 47 the product goes beyond the given constraints. 2*3*5*7*11*13*17*19*23*29*31*37*41*43*47*53 = 32589158477190044730

Akshat_101 + 1 comment what does for(int i : prime) do in your code?

nockzblack + 0 comments It's like a for x in array in pyhton

- AA
agrawala790 + 0 comments I have posted my solution in java and passed all the test cases without using biginteger...

mike006322 + 0 comments I was able to get around this by coding that if n is large then divide n by the first k primes and in that case incriment my unique prime counter by k.

lkutsarov + 0 comments The real challenge is to make it without a ready set of prime numbers and not timing out.

- AG
Gozalishvili_ANZ + 1 comment hello guys.. I thing it would be better to remember primes in array using sieve of eratosthenes algorithm, and then cycle through this array multiplying each prime until we get higher number then given number.. the number of used primes minus one will be answer of this solution...

- KW
kenrickj84 + 1 comment why not just remember their products?

parsiad + 0 comments As per kenrickj84's comment:

import bisect products=[1] for prime in [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53]: products.append(prime*products[-1]) for _ in range(int(input())): print(bisect.bisect_right(products,int(input()))-1)

CooL_codeR97 + 2 comments This is very easy approach for this problem

prime=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] for i in range(int(input())): count,result=0,1 n=int(input()) for j in prime: result*=j if(result<=n): count+=1 print(count)

deepak_097 + 0 comments thanks for the idea

nachomonllor + 0 comments very nice

ebrucecfa + 0 comments Interesting problem. Although I would add that you do have to experiement with the primes array (at least in Java 8) to pass all test cases.

The below function passes all test cases - including the troublesome 11, 16 and 17.

static void countPrimeFactors(long N){ long primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; int count = 0; long pf = primes[0]; for(int j = 1; j < primes.length && pf <= N && N != 1; j++){ pf = pf * primes[j]; count++; } System.out.println(count); } // countPrimeFactors

Note that if you use the below primes array, you will fail 11, 16 and 17.

long primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};

Also, if you use a larger primes array (eg Primes from 2 to 59 or greater), you will also fail test cases 11, 16, 17.

tl;dr - In Java 8, passing all test cases is dependent on using Primes array from 2 to 53. You will faile test cases 11,16 and 17 using other array constituents.

- PT
peterteach + 1 comment All my attempts at doing this in pure Python3 have some test time out.

- C
cabarrap + 0 comments I have the same problem

Sort 112 Discussions, By:

Please Login in order to post a comment