Sieve of Eratosthenes is a fast algorithm for finding prime numbers in larger ranges. According to W…
Click here to read the complete problem statement.
If you need help solving this problem, mention your approach and ask specific questions. Please avoid sharing your code and asking the Community to figure out “what’s wrong”.
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?
@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: Sieve of Eratosthenes: A Number Theory Tutorial | Toph Tutorials
May be a simple problem…
But my code is wrong 
My code is below 
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 
@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: Sieve of Eratosthenes: A Number Theory Tutorial | Toph Tutorials.
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.
@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.
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.
@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.
lol
you really adjusted it roughly to the limit?
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.
Changed CPU factor for Python languages to 3×.
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.
@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.
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.
WoW! Since I started with Python3, I didn’t know it.
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?
# 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…
@hjr265 ভাই। সেম কোড আজ রান করাতে টিএলই আছসে। এটা শর্টেস্ট সাবমিশন।
আমার মনে হয় পাইথন সব ৫x রাখা দরকার।
https://toph.co/s/491267