Sort 21 Discussions, By:
Please Login in order to post a comment
Don't try to find every number's prime factors, you have no chance not to get timeout errors.
Think about sieve of eratosthenes algorithm. Don't you go through all numbers with each prime. That's the trick.
Really good hint. It reveals enough insights without directly giving away the solution.
Test your solution :
I am a bit confused regarding the following test case: 37 2
There are 4 consequtive numbers which have 2 distinct prime factors:
33: [3, 11]
34: [17, 2]
35: [5, 7]
36: [2, 3]
Which is the expected answer for this range?
Hey statement says "Print the first of these numbers in ascending order."
Please tell me what is confusing in this?
Because if it's more than k, is that really considered k-consecutive? I would not have initially counted any of those, however the solution clearly considers 33, 34 and 35 in this case.
Can you tell me the answer to my question please? So I can tell you what is confusing :)
Thanks for the answer! This clarified the problem statement a lot!
However I suggest an improvement in the description by including this exactly case to the test cases.
why isnt 15 included in the answer ???
16 = 2^4 only 1 distinct prime is there
For those who were wondering how to use sieve of eratosthenes here, this is the my modified sieve function
for powers of a prime number n (not including the prime itself), A[n] will be 0
for other numbers, A[n] will be one larger than the number of distinct prime factors
A=3 (since 12 has 2 distinct prime factors 2 and 3),
A=4, so 1001 should have 3 distinct prime factors (indeed 7,11,13)
A = *(n+1)
A, A = 0, 0
for i in range(2,n+1):
if A[i] == 1:
for idx in range(1,n//i+1):
for po in range(2,int(math.log(n,i))+1):
A[i**po] = 0
May you help me to understand? How can you assert the primes won't be repeated in the following consecutives?. Let's say, increasing N and K.
Wonderful challinging PE 47 problem version. Took my 3 hours to adapt sieve of eratosthenes but now I'm one step closer to stopping being a brute!
The example says 644 has prime factors of "2^2 x 7 x 23".
We know 2 is a prime number. But how is 2^2 a prime factor? It equals 4, which is not a prime number.
And the sample test case says 20 has 2 distinct prime factors. What are they? It can't be 4 and 5, because 4 isn't prime. It can't be 2 and 10, because 10 isn't prime. Is it 2^2 and 5? If so, why is 2^2 allowed, and what are the rules regarding exponents when it comes to prime factors?
Look at it this way. A number has some prime factors, if factors are repeating they are shown as powers.
Example 36 = [2,2,3,3] which you can represent as 2^2 * 3^2, it is 2 distinct factors
How are 319143, 352884, 389388 are wrong results for k=4???
The approach to solving this problem gave me a very familiar feeling, and got me looking up all previous problems...until I finally found out it was Codeforces 959D. Anyway, it's a nice example to use for-break-else in Python.
How to use sieve of eratosthenes algorithm in this. It will definitely go out of time.
Finally got my ans using eratosthenes algorithm :)