Looking for proportion of prime numbers in a list, error in code

Question

I'm trying to solve this Project Euler task which is to find the point at which the proportion of primes in a list drops below a certain percentage (the diagonals in this spiral of numbers below).

I generated primes up to a point, then compare the list of numbers to it, but the answer I get is much, much lower than the correct answer, and I don't know why. My answer was 631 (for below 10%), correct answer is 26000 something.

I know my approach doesn't work because it's too slow, so I'll redo that, but I also want to know why I'm getting the wrong answer anyway.

len_limit = 6 # for generating primes. I've adjusted this limit based on how far I get up to
limit = 10 ** len_limit 
primes2 = [True] * (limit + 1)
primes2[0] = primes2[1] =  False
for i in range (2,int(limit ** 0.5) + 1):
    for n in range(2, int(limit / i) + 1):
        primes2 [i*n] = False
primes = []
for i in range(len(primes2)):
    if primes2[i] == True:
        primes.append(i)

def make_square(side_length): # making all the numbers into a list
    a,b = 0,0
    nums = [1]
    square_size = side_length
    for n in range(2,square_size): 
        nums.append(4 * n ** 2 - 10 * n + 7)    # NE
        nums.append((2*n - 1) ** 2)             # SE
        nums.append(4 * n ** 2 - 8 * n + 5)     # NW
        nums.append(4 * n ** 2 - 6 * n + 3)     # SW
    nums.sort()
    return nums

def fraction_prime(side_length):
    nums = make_square(side_length)
    a,b = 0,0
    for num in nums:
        if num in primes:
            a += 1
            b += 1
        else:
            b += 1
    return (a/b)

i = 3
while True:
    i += 1
    fraction_prime(i)
    side_length = 2 * i - 3
    # print(fraction_prime(i),side_length,i) # optional, just to check that it was working
    if fraction_prime(i) <= 0.40: # not the number needed in the question, just to see if it works
        print(fraction_prime(i),side_length,i)
    if fraction_prime(i) < 0.40:
        break

it would be interesting also to monitor the ratio of primes along the diagonals VS all primes in the square — cards
– cards, Commented Nov 24 at 15:38

Apichet Janya · Accepted Answer · 2025-11-23 07:43:16Z

3

Your prime table only goes up to 1,000,000, but the diagonal values in the spiral grow much larger (hundreds of millions).
Anything above your limit is automatically treated as “not prime”, so your ratio drops way too early — that’s why you get ~631 instead of ~26,000.

if num in primes on a list is O(n)O(n)O(n). Since you already have primes2, use primes2[num] instead.

To get the correct answer, you must

generate primes up to the largest diagonal value, or
skip the big sieve and test each diagonal value with a simple primality check.


def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True


prime_count = 0   
diag_count = 1    
layer = 0 


TARGET_NUM = 1
TARGET_DEN = 10

while True:
    layer += 1
    side_length = 2 * layer + 1  
    high = side_length * side_length  
    step = side_length - 1      


    for k in range(4):
        val = high - k * step
        if is_prime(val):
            prime_count += 1

    diag_count += 4


    # prime_count / diag_count < 1/10  <=>  10 * prime_count < diag_count
    if TARGET_DEN * prime_count < TARGET_NUM * diag_count:
        print("=== Result ===")
        print(f"Layer        : {layer}")
        print(f"Side length  : {side_length}")
        print(f"Prime count  : {prime_count}")
        print(f"Diag count   : {diag_count}")
        print(f"Prime ratio  : {prime_count / diag_count:.12f}")
        break

print("Done.")

answered Nov 23 at 7:43

Apichet Janya

1111 silver badge2 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dominic Nov 23 at 9:53

Hey thanks, so it was just that. I think in my head I confused the length of the sides with the actual numbers I was using, so was confused why the limit I thought was enough was still giving me errors. Thank you for your time and explanation.

Apichet Janya Nov 23 at 10:07

You're very welcome, I'm glad it helped! And yes, it's an easy thing to mix up; the side length grows linearly, but the diagonal values grow like, so they shoot past the prime limit much faster than expected. good luck with the rest of the problem!

Martin Brown · Accepted Answer · 2025-11-23 10:26:09Z

This is one of those puzzles where the obvious way of doing it with an explicit square array of numbers most of which are not prime is impossibly slow.

You only need to consider and test the numbers that occur on three of the four diagonals of the square and they can be generated quickly for any position away from the centre of the square by a simple difference algorithm (or a formula). Difference method is usually faster.

The diagonal sequences with their first and second differences shown are:

1   3    13    31    57    91     
  2   10    18    26    34
    8     8     8     8     8

1   5    17    37    65   101
  4   12    20    28    36
    8     8     8     8

1   7    21    43    73    111
  6   14    22    30    38
    8     8     8     8     

1   9    25    49    81    121
  8   16    24    32    40
    8     8     8     8

The final one of these four diagonals can be ignored since they are all squares of the odd numbers. The generating rule is add an even number that is incremented by 8 each time.

Code snippet to generate the diagonal numbers that need to be checked:

  n3 = 1
  delta_n3 = 2
  n5 = 1
  delta_n5 = 4
  n7 = 1
  delta_n7 = 6
  
  for s in range(side_length)
      n3 += delta_n3
      n5 += delta_n5
      n7 += delta_n7
      delta_n3 += 8
      delta_n5 += 8
      delta_n7 += 8

And with a bit of cunning you can also zap all the values that divide by 3 from the n3 and n7 streams. And a bit more difficult you can zap divides by 5 from the n5 stream.

NB isprime need not consider divides by 2 since it cannot arise in this problem.

Collectives™ on Stack Overflow

Looking for proportion of prime numbers in a list, error in code

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related