Correct the Sieve

Toph Problems
#1

Limits: 1s, 512 MB

Sieve of Eratosthenes is a fast algorithm for finding prime numbers in larger ranges. According to Wikipedia, the algorithm works as follows:

This is a companion discussion topic for the original entry at https://toph.co/p/correct-the-sieve
1 Like
#2 
import math
N=int(input())
i=0
a=2
d=0
while i!= N:
    m=int(input())
    s=math.sqrt(m)+1
    while a<=s:
        if m%a==0 and m!=2 and m!=3:
            print(m,"is not a prime number.")
            d=1
            break
        a+=1
        if a==m+1:
            break
    if d!=1 or m==2 or m==3:
        print(m,"is a prime number.")
        d=0
    d=0
    a=2
    i+=1

I used this code. It shows CLE on the last check. What can I do about this?

#3

@Rafeed Can you try a more efficient approach?

The square root approach is okay, but I don’t think it is efficient enough for this problem.

You can learn about Sieve of Eratosthenes here: https://toph.co/tutorials/sieve-of-eratosthenes

#4

May be a simple problemâ€Ļ
But my code is wrong :worried:

My code is below :arrow_down:

 is_prime = True
loop = int(input())
for j in range(loop):
    num = int(input())
    
    for i in range(2, num):
        if num % i == 0:
            is_prime = False
            break

    if is_prime:
        print("{} is a prime number.".format(num))
    else:
         print("{} is not a prime number.".format(num))
#Plz fix my wrong..

It is tough to catch my wrong to me cause of my using Android device :frowning_face:

#5

@corrupted_brain This solution is too naive. You will need to implement a more efficient solution for this problem.

Sieve of Eratosthenes is what you need here. You can learn about Sieve of Eratosthenes here: https://toph.co/tutorials/sieve-of-eratosthenes.

#6

@hjr265

https://toph.co/s/308193

N=1000100
b=[1]*N
b[0]=b[1]=False
i=2
while i*i<N:
	if b[i]:
		for j in range(i*i,N,i):b[j]=False
	i+=1
for i in range(int(input())):
	i=int(input())
	if b[i]:print("%d is a prime number."%(i))
	else:print("%d is not a prime number."%(i))

If this doesn’t work, that means there is no way to solve this problem in python.

#7

@touhidur You are right. Looks like this problem’s limits were never adjusted for Python’s run-time overhead.

I will make it so that Python and PyPy executions get 3 times more CPU.

#8

image
image1196×1279 27.1 KB

@touhidur Your recent submissions for this problem has been rejudged.

1 Like
#9

I was going to ask you about adjusting Python runtimes.
You seem to adjust it a little.
However, with this adjustment, I can’t see the exact runtime.

#10

@touhidur When a language is given a CPU factor of X (e.g. X = 2.75), and your submission has used C seconds of CPU (e.g. C = 0.9), then the true usage of CPU is:

X * C = 2.75 * 0.9s = 2.47s

To make things less confusing for a solver, Toph only shows the scaled usages (CPU and memory) to them.

#11

lol
you really adjusted it roughly to the limit?
:rofl:

#12

Yes. For some reason, PyPy can optimize the square-root solution to this problem really well. I don’t think the author intended for the square-root solutions to pass for this problem. Hence the limit.

#13

Changed CPU factor for Python languages to 3×.

#14

Yes, in my personal tests, square root version of sieve works faster than other easier versions. (at least in C and C++). That’s why my submission was judged as the fastest I guess.
When I first solved the problem, I just required to replace 1 character from the Author’s code to get AC. So, the original code doesn’t need to be altered that much in order to solve this problem.

However, thanks from all Python users for altering the CPU Limit for Python.

1 Like
#15

@hjr265 I see the increase of CPU limit.
But this time the code shows WA in the first test. Code slightly changed for showing 1 as a non prime number, still showing different results is kinda ridiculous. uDebug outputs matches with custom output btw.

#16

image
image2988×1796 210 KB

This is interesting. So notice how you are printing tuples instead of strings.

In Python 3, print is a function. And so to print something, you write print(X).

In Python 2, print is a keyword. And so to print something, you write print X. If you write print(A, B), it prints a tuple.

#17

WoW! Since I started with Python3, I didn’t know it.

#18

The statement a says that number of test cases is an int. So what’a the maximum range of it? 32767? My code in c produces correct outputs as long as number of test cases is within 10^5.
But when I type in 10^6 it crashes and gives me RE. I am storing the values of each test case in an array. But the program can’t declare an array with 10^6 size and larger. This happens when I try to solve other problems with similar parameters too. How do I solve it? Is there a limit in c for array declaration?

#19 
# importing_port
from math import ceil   # look up python docs
from itertools import compress  # kinda works like "".join()


# defining_port


def sieve(limit):
    if limit < 2:
        return []

    limit += 1      # Pre-increment `limit` so sieve is inclusive, unlike `range`.
    primes = [True]*limit       # declaring every element [TRUE]
    for base in range(2, int(limit**0.5 + 1)):
        if primes[base]:               # vv declaring multiples of prime numbers as [FALSE] vv
            primes[base*2:limit:base] = [False]*(ceil(limit / base) - 2)

    primes[0] = primes[1] = False
    return compress(range(limit), primes)

# main_port


prime_list = list(sieve(15485863))
repeat = int(input())

for i in range(repeat):
    n = int(input())

    if n in prime_list:
        print(n,"is a prime number.")
    else:
        print(n,"is not a prime number.")

this code of mine, gets stuck on the 6th case, can anyone please explainâ€Ļ

#20

@hjr265 āĻ­āĻžāĻ‡āĨ¤ āĻ¸ā§‡āĻŽ āĻ•ā§‹āĻĄ āĻ†āĻœ āĻ°āĻžāĻ¨ āĻ•āĻ°āĻžāĻ¤ā§‡ āĻŸāĻŋāĻāĻ˛āĻ‡ āĻ†āĻ›āĻ¸ā§‡āĨ¤ āĻāĻŸāĻž āĻļāĻ°ā§āĻŸā§‡āĻ¸ā§āĻŸ āĻ¸āĻžāĻŦāĻŽāĻŋāĻļāĻ¨āĨ¤
āĻ†āĻŽāĻžāĻ° āĻŽāĻ¨ā§‡ āĻšā§Ÿ āĻĒāĻžāĻ‡āĻĨāĻ¨ āĻ¸āĻŦ ā§Ģx āĻ°āĻžāĻ–āĻž āĻĻāĻ°āĻ•āĻžāĻ°āĨ¤
https://toph.co/s/491267