Функция Python для простого числа - PullRequest
Новая
       7

Функция Python для простого числа

0 голосов
/ 21 октября 2018

Я хочу написать функцию, которая возвращает количество простых чисел, которые существуют до и включая данное число.Функция count_primes (100) должна возвращать 25

Я написал код, который дает 23 вместо 25. Функция пропускает 41 и 71 при подсчете всех других простых чисел в диапазоне от 1 до 100. Может кто-нибудь объяснить, почему мой кодпропускает 41 и 71. Мой код 

import math
def count_primes(num):
    current_number = 4
    number_of_prime = 2
    while current_number <= num:
        is_prime = True
        if current_number%2==0:
            is_prime = False
            current_number += 1
            continue
        else:
            limit = math.ceil(current_number ** 0.5)+1
            for i in range(3, limit, 2):
                if current_number%i==0:
                    is_prime = False
                    current_number += 1
                    continue
        if is_prime == True:
            print(current_number)
            number_of_prime += 1
        current_number += 1
    return number_of_prime
count_primes(100)

У меня есть еще одна функция, которая отлично работает.Я просто хочу знать, почему этот код пропускает только 41 и 71.

Ответы [ 2 ]

0 голосов
/ 21 октября 2018

Проблема заключается в вашем внутреннем цикле: 

for i in range(3, limit, 2):
    if current_number%i==0:
        is_prime = False
        current_number += 1
        continue

Оператор continue здесь продолжает только внутренний цикл, а не внешний.Это означает, что всякий раз, когда вы проверяете составное число, оно увеличивается на current_number, но не возвращается к проверке делимости на 2.

Например, при итерации внешнего цикла, который начинается с current_number == 39,код находит, что он делится на 3, поэтому он увеличивает current_number до 40 и продолжает внутренний цикл, а не внешний.Таким образом, он проверяет 40 на делимость на 5, но не на 3. И поскольку 40 делится на 5, он продолжает проверять 41 на делимость на 7. Конечно, 41 не делится на 7, но is_prime все еще False сзади, когда код обнаружил, что 39 делится на 3, поэтому 41 не печатается.

Это довольно своеобразная комбинация обстоятельств, которая влияет только на 41 и 71 в диапазоне, в котором вы находитесьтестирование, потому что они следуют за последовательностями нескольких достаточно больших составных чисел, а именно 39,40 и 69,70.

Я бы предложил выполнить упражнение для самостоятельной работы: поместите операторы печати там, где вы проверяете делимость, ивы увидите, что происходит ясно.Например: 

print('testing {} for divisibility by 2: {}'.format(current_number, current_number % 2 == 0))
if current_number%2==0:
    is_prime = False
    ...

и позже 

print('testing {} for divisibility by {}: {}'.format(current_number, i, current_number % i == 0))
if current_number%i==0:
    ...
0 голосов
/ 21 октября 2018

Исправлен код и добавлен комментарий: 

import math
def count_primes(num):
    current_number = 4
    number_of_prime = 2
    while current_number <= num:
        is_prime = True
        if current_number%2==0:
            is_prime = False
            current_number += 1
            continue
        else:
            limit = math.ceil(current_number ** 0.5)+1
            for i in range(3, limit, 2):
                if current_number%i==0:
                    is_prime = False
                    #current_number += 1 #first increment
                    continue
                    #This continue statement does not skip the next lines (after the for loop) so you increment current_number twice
        if is_prime == True:
            print(current_number)
            number_of_prime += 1
        current_number += 1 #second increment
    return number_of_prime
count_primes(100)
...