is it possible to solve this problem in python >_

swastik_P's blog

By swastik_P, history, 3 hours ago, In English

https://www.spoj.com/problems/TDPRIMES/ https://www.spoj.com/problems/HS08PAUL/

it is too slow in python with sieve

if someone knows a way to optimize it or a trick then please tell me!!!!

swastik_P
3 hours ago
10

Comments (10)

Write comment?

Kalikhan-Adil

2 hours ago, hide # |

In Python, if you try to check every number one by one to see if it’s prime, it’ll take forever. You have to use a trick called the Sieve of Eratosthenes. Think of it like this: you lay out all numbers from 2 to 100 million. You start at 2 and cross out every 2nd number (4, 6, 8...). Then you go to 3 and cross out every 3rd number. By the time you’re done, only the primes are left standing.

→ Reply

swastik_P

2 hours ago, hide # ^ |

actually i did tried sieve,

but it was not working!!, it still took a hell lot of time!

→ Reply

swastik_P

2 hours ago, hide # ^ |

to me, sieve always gives TLE

like there is this very simple problem

i used python template of sieve and implemented it here https://www.spoj.com/problems/VECTAR8/

#template of sieve made with help of cp-algorithm and ai
import math

def count_primes(n: int) -> int:
    S = 10000

    primes = []
    nsqrt = int(math.sqrt(n))
    is_prime = [True] * (nsqrt + 2)

    for i in range(2, nsqrt + 1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * i, nsqrt + 1, i):
                is_prime[j] = False

    result = 0
    block = [True] * S

    k = 0
    while k * S <= n:
        for i in range(S):
            block[i] = True

        start = k * S

        for p in primes:
            start_idx = (start + p - 1) // p
            j = max(start_idx, p) * p - start
            while j < S:
                block[j] = False
                j += p

        if k == 0:
            block[0] = False
            block[1] = False

        i = 0
        while i < S and start + i <= n:
            if block[i]:
                result += 1
            i += 1

        k += 1

    return result
    
#my original code
for i in range(int(input())):
	print(count_primes(int(input())))

and even it gave tle!

→ Reply

explainer

56 minutes ago, hide # ^ |

The problem is not the sieve, the problem is your algorithm. There are only 671 of these numbers in the range. You can generate them all quickly with backtracking and a sieve.

→ Reply

lalitt

2 hours ago, hide # |

maybe use bytearray in python, generally python is too slow to run for 1e8 sieve tho

→ Reply

swastik_P

2 hours ago, hide # ^ |

hey i have tried every single thing possible, bytearray took a lot less time , but still thrice the limit and TLE

→ Reply

swastik_P

113 minutes ago, hide # ^ |

import math

#imported template (copied)
def primes(n):
    if n < 2:
        return []

    # only keep track of odd numbers
    # index i means number (2*i + 1)
    s = bytearray(b"\x01") * (n // 2 + 1)
    s[0] = 0   # 1 is not prime

    limit = math.isqrt(n)

    for i in range(1, limit // 2 + 1):
        if s[i]:
            p = 2 * i + 1
            start = p * p // 2
            s[start::p] = b"\x00" * ((len(s) - start - 1) // p + 1)

    ans = [2]
    for i in range(1, len(s)):
        if s[i]:
            ans.append(2 * i + 1)

    return ans


# my original solution
x = primes(10**8)
print(len(x))
print(x[:10])
print(x[-10:])

took more than 2 seconds on 4090rtx MSI katana, and their system is intel club so it would probably take 10-15 seconds