# Project Euler #47: Distinct primes factors

# Project Euler #47: Distinct primes factors

mahmut_eren72 + 1 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.

amitsowani + 0 comments Really good hint. It reveals enough insights without directly giving away the solution.

tasyrkin + 7 comments 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?

`33 35`

OR

`33`

shashank21jHackerRank AdminChallenge Author + 1 comment Hey statement says "Print the first of these numbers in ascending order."

Please tell me what is confusing in this?cantonios + 0 comments 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.

tasyrkin + 0 comments Can you tell me the answer to my question please? So I can tell you what is confusing :)

shashank21jHackerRank AdminChallenge Author + 0 comments For

`37 2`

Answer is

`14 20 21 33 34 35`

tasyrkin + 0 comments 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.

abhi1agarwal + 1 comment why isnt 15 included in the answer ???

thigwyd + 0 comments [deleted]

shashank21jHackerRank AdminChallenge Author + 0 comments @abhi1agarwal

16 = 2^4 only 1 distinct prime is thereIAmHacker1 + 0 comments 33 34 35

dingma129 + 1 comment 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

for example,

A[4]=0,

A[12]=3 (since 12 has 2 distinct prime factors 2 and 3),

A[1001]=4, so 1001 should have 3 distinct prime factors (indeed 7,11,13)

def sieve(n): A = [1]*(n+1) A[0], A[1] = 0, 0 for i in range(2,n+1): if A[i] == 1: for idx in range(1,n//i+1): A[i*idx]+=1 for po in range(2,int(math.log(n,i))+1): A[i**po] = 0 return A

rafapr1212 + 0 comments 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.

tieros + 0 comments 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!

Matt_Scandale + 1 comment 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?

shashank21jHackerRank AdminChallenge Author + 0 comments 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

jvdsouza1123 + 0 comments I have read the description several times now and can't seem to understand. Here is one of the input/output sample tests.

Sample Input#00 20 2

Sample Output#00 14 20

Why are the following not considered as output (I printed the first 2 results in ascending order):

6 = 2 x 3

10 = 2 x 5

lucky_21 + 0 comments How are 319143, 352884, 389388 are wrong results for k=4???

kitchent + 0 comments 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.

Lehar_Jain + 0 comments How to use sieve of eratosthenes algorithm in this. It will definitely go out of time.

Sort 22 Discussions, By:

Please Login in order to post a comment