ian16 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 awesome logic.
fheil0815 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 Nice
ranjan_purbey Could you please explain how this works?
tpgreene 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)
tpgreene 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.
tpgreene [deleted]
tarasyaremabcn 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 [deleted]Ankit_ISM_1997 Unique Solution
LINKONRUHUL [deleted]
mitkonikov01 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; }
alex_pn 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 Yeah, you can allways can go for a python solution or a bigint implementation on the C code. Nice that you noticed it!
einsteinFan upto 47 is enough
jainsajal1301 Not valid when n is itself prime..
bak_karolek You can always divide n and check if it is > 0 istead of multiplying temp. There is no risk of overflow then.
bennattj 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 The same approach, just lazy calculation with long overflow check.
afando 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 If you use Java, you need BigInteger to store multiplied values, if you don't use you cannot pass TC 11,16 and 17.
agollapudi2019 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 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); }
vaibhav_6451956 why you stopped taking primes beyond 47?
KeyurPotdar 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 what does for(int i : prime) do in your code?
nockzblack It's like a for x in array in pyhton
agrawala790 I have posted my solution in java and passed all the test cases without using biginteger...
mike006322 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 The real challenge is to make it without a ready set of prime numbers and not timing out.
Gozalishvili_ANZ 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...
kenrickj84 why not just remember their products?
parsiad 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 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 thanks for the idea
nachomonllor very nice
ebrucecfa 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.
peterteach All my attempts at doing this in pure Python3 have some test time out.
cabarrap I have the same problem
Sort 112 Discussions, By:
Please Login in order to post a comment