swastik_P's blog

is it possible to solve this problem in python >_
By swastik_P, history, 6 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!!!!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    5 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    actually i did tried sieve,

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

    → Reply
  • »
    »
    5 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      4 hours ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        77 minutes ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        hey, can you please provide me it's python based solution!

        it will be really helpful for me

        → Reply
        • »
          »
          »
          »
          »
          57 minutes ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          This is the code I used to count the numbers. It runs in 0.1s in my laptop.

          MAXN = 10 ** 6

is_prime = [True] * (MAXN + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, MAXN + 1):
    if is_prime[p]:
        for m in range(p * p, MAXN + 1, p):
            is_prime[m] = False

res = []
def search(x=0, p=1):
    if x:
        res.append(x)
    for d in range(1, 10):
        nx = p * d + x
        if nx <= MAXN and is_prime[nx]:
            search(nx, p * 10)

search()

res.sort()
print(len(res))
print(res)
          → Reply
»
5 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    5 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it 
    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

    → Reply
»
4 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

that's why in competitive programming you should use c++ and shouldn't use python

→ Reply
  • »
    »
    4 hours ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    yeah but i think c++ is wayy too diffcult and complex,

    i find python easier and simpler+faster to code in, it gives me advantage when i have to solve a problem fast, and took Pajenegod as a idol

    btw if you have any resource to learn c++ ASAP then please provide it , i will start learning c++ now

    → Reply
»
2 hours ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I know that typing in Python better, but trust me:

It's better to learn C++! If you really want to go to the EJOI/IOI/ICPC, you must learn C++:

Time Limit Exceeded (TLE):

In CP, TLE is your best friend if you use Python. C++ gives you a massive 'safety buffer' because of its raw execution speed.

The STL Advantage:

C++ STL is designed for performance and efficiency. While you're looking for a library to balance your tree, I've already solved the problem using std::map and std::set.

Efficiency:

A $$$O(N^2)$$$ solution in C++ sometimes passes where a $$$O(N \log N)$$$ in Python fails. That's how much of a gap we're talking about.

Memory Overhead:

Python’s memory management is too bloated for tight constraints. C++ is lean and mean.

→ Reply
  • »
    »
    74 minutes ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    yeah, i am facing lot of such issues at spoj, but in my country grade 1 local olympiad for national selection will happen right after 1 months, so i dont think i will get comfortable with c++ in that time

    but is there a way to learn it in 1 month?

    edit

    wait really!, O(N^2) compared to O(N LOG N)!!!, by this logic i think i can almost never get tle at c++!!, please provide me a e-book or a website to learn c++

    → Reply
    • »
      »
      »
      27 minutes ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Umm, i think the best way to learn is AI. But, you need to control yourself + say him, that you need C++ for CP. I learned from CodeChef, but right now almost all courses need payment... RIP CodeChef :sob:.

      → Reply
    • »
      »
      »
      6 minutes ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      At your level python is fine. Focus on learning the basics of problem solving, algorithms and data structures.

      You can switch to C++ in the future, if you think python is holding you back.

      → Reply