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.
Project Euler #47: Distinct primes factors
Project Euler #47: Distinct primes factors
Sort by
recency
|
29 Discussions
|
Please Login in order to post a comment
Python
In python 0 is false and 1 is true
JAva Code
After a day of googling, I had realized this:
If you use common codes to find prime factors like here: https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/ , you cannot pass all test cases coz its time complexity = O(n^0.5) (I though it was the fastest algorithm ever but I was wrong)
If you use a more efficient algorithm like here: https://www.geeksforgeeks.org/efficient-program-print-number-factors-n-numbers/?ref=rp , you can pass coz it's only O(logn)
C++ Solution :
First find the number of different prime factors of all numbers in range [2,2000000] using an algorithm similar to sieve of eratosten. Then for each test case, iterate over all numbers from 2 to N and check is there is an answer or not.