What is the problem with my code for finding whether a number is prime or not

Question


N = int(input())
flag = False
if N <= 2:
  print('no')
for j in range(2, int(N**0.5)+1):
  if N%j == 0:
    flag = True
if flag == False:
  print('yes')
else:
  print('no')

The logic is same everywhere I saw the solution, but somehow codechef shows that it is a wrong answer, as I don't have a pro subscription of codechef, I cannot see the failed cases.

There's no need for `else: pass`. Just leave out the `else:` block entirely. — Barmar, Mar 28 '23 at 15:01
`for j in range(2, N):` => `for j in range(2, int(N**0.5)+1):` to break the complexity, then break if your flag is true — Jean-François Fabre, Mar 28 '23 at 15:03
I did that and then too it shows an error. Memory used is 9.6M and time is 0.04s — Xyls047, Mar 28 '23 at 15:05
even better, it could break when the flag is made True (since it's found a prime divisor) to not have to iterate through unnecessary checks. — alexhroom, Mar 28 '23 at 15:13

score 2 · Answer 1 · answered Mar 28 '23 at 15:04

2

Welcome to StackOverflow! This code is along the right lines (although could be done far more efficiently) for any number above 2, but look at the edge cases - this script gives the result that both 1 and 0 are prime numbers.

answered Mar 28 '23 at 15:04

alexhroom

173
8

0 is not in problem domain, but 1 is worth checking. – matszwecja Mar 28 '23 at 15:09
I added an if statement above the for `for` loop, to rule out the edge cases, then too it shows wrong answer – Xyls047 Mar 28 '23 at 15:10
1

@Xyls047 could you please add the wording of the problem you're solving, or a link to the problem on CodeChef? This may also be an issue with the answer CodeChef is expecting to see. – alexhroom Mar 28 '23 at 15:12
@alexhroom This is the link for the CodeChef problem : https://www.codechef.com/problems/PRB01?tab=statement – Xyls047 Mar 28 '23 at 15:16
1

@Xyls047 You consider both 1 and 2 not prime? – Fractalism Mar 28 '23 at 15:20

Asi · Accepted Answer · 2023-03-28T15:35:03.640

0

N = int(input())
flag = False
for j in range(2, N):
    if N % j == 0:
        flag = True
if not flag and N > 1:  # Important: 0 and 1 are not prime numbers
    print('yes')
else:
    print('no')

edited Mar 28 '23 at 15:35

answered Mar 28 '23 at 15:09

Asi

170
2
10

2

I would like to know what was the mistake with my piece of code, where did I go wrong – Xyls047 Mar 28 '23 at 15:20
0 and 1 are not prime numbers, which is a special case inside the logic – Asi Mar 28 '23 at 15:36

What is the problem with my code for finding whether a number is prime or not

2 Answers2