for j in range(1, i + 1):
вы стабильно делите на 1, а на 1 делится любое число, поэтому вы получаете неверный ответ
вы стабильно делите i
на i
, поэтому и тут получаете неверный ответ (увеличение счетчика):
в вашем коде надо так:
for j in range(2, i):
дальше вы по сути считаете ДЕЛИТЕЛИ, а не определяете простое число, вам надо делать так:
isPrime = True
for j in range(2, i):
if i % j == 0:
isPrime = False
break
if isPrime:
c += 1
или сделать от обратного
for j in range(2, i):
if i % j == 0:
с += 1
break
...
res = (n - a) - c
P.S.
если говорить про оптимизацию кода без использования внешних библиотек, то не надо проверять делимость анализируемого числа i
на все числа от 2 до i - 1
, надо проверить лишь от 2
до ceil(sqrt(i))
:
for j in range(2, int(i**.5) + 1):
правда тут надо отдельно обработать ситуацию для i = 2
, потому что при таком подходе не будет произведено ни одного подсчета