CODEWITHSUNDEEP
python
Daquicker
Daquicker

Reputation: 525

euler challenge 12, why does this python code fail?

The Following code keeps telling me a wrong number and I can't see why, know it's brute force but it should still work... also the number it returns has indeed over 500 divisors, 512 to be exact, help would be much appreciated 

Number = 1
Count = 2
Found = False
while Found == False:
    Divisors = 0
    if (Number % 2) != 0:
        for i in range(1, int(Number**(1/2)), 2):
            if Number % i == 0:
                Divisors += 1

    else:
        for i in range(1, int(Number**(1/2))):
            if Number % i == 0:
                Divisors += 1

    if Divisors >= 500:
        print (Number)
        Found = True

    else:
        Number += Count
        Count += 1

For reference: Problem 12 from the Euler Challange

Upvotes: 1

Views: 231

Answers (4)

rewritten
rewritten

Reputation: 16435

The number of divisors of an integer is just the product of (1 + exponent) for each pure power in the factor decomposition of an integer.

As an example: 28 = 2^2 * 7

The powers are 2 and 1, so the number of divisors is (2+1)*(1+1) = 3*2 = 6. Easy one

Bigger one: 2047 * 2048 / 2 = 2^10 * 23 * 89

The powers are 10, 1 and 1, so the number of divisors is 11*2*2 = 44

Easier: 100 = 2^2 * 5^2

The powers are 2, 2 so there are 3*3=9 divisors. The same applies to 36=2^2*3^2. The only interesting part is the exponents.

So, use any prime factor decomposition (use a sieve, you don't need a primality test) it would be much faster and more reliable than trying each of the possible numbers.

def factorize(i):
    # returns an array of prime factors
    whatever

def number_of_divisors(i):
    n = 1
    for v in Counter(factorize(i)).values():
        n *= v + 1
    return n

Upvotes: 3

wtayyeb
wtayyeb

Reputation: 1959

the code you have been write is searching till number**0.5 and it is wrong you must search until number/2 so the corrected answer is like below:

Note : I add some extra code to show the progress. and they are not affect the solution.

Another Note: since the Nubmer itself is not counted like in the problem example, I add once to perform that.

Number = 1
Count = 2
Found = False
big_Devisor = 0
print "Number   Count   Divisors" 
while Found == False:
    Divisors = 1  # because the Number is itself Devisor
    if (Number % 2) != 0:
        for i in range(1, int(Number/2), 2):
            if Number % i == 0:
                Divisors += 1
    else:
        for i in range(1, int(Number/2)):
            if Number % i == 0:
                Divisors += 1

    if Divisors >= 500:
        print (Number)
        Found = True

    else:
        if Divisors > big_Devisor:
            big_Devisor = Divisors
            print Number,'\t', Count, '\t', Divisors 
        Number += Count
        Count += 1

Upvotes: 1

Daniel Fischer
Daniel Fischer

Reputation: 183878

Your divisor counting method is wrong. 12 has 6 divisors, but your code only counts 2.

Problems:

  1. a number often has divisors larger than its square root
  2. range doesn't include its upper bound, so you're stopping too early

Upvotes: 2

Abe Schneider
Abe Schneider

Reputation: 987

I'm not sure what Euler Challenge 12 is, but one obvious issue is the (1/2). If you try typing that in a Python prompt, you'll get 0. The reason why is that it will try to do integer math. I suggest just putting (0.5), or alternatively you could do (1/2.0).

Upvotes: 2

Related Questions