Как рассчитать первые n простых чисел?

Question

Предпологаем наличие функции is_prime. Предположим, что переменная n была связана с положительным целым числом. Напишите операторы, необходимые для вычисления суммы первых n простых чисел. Сумма должна быть связана с общей суммой переменных.

Примечание: is_prime принимает целое число как параметр и возвращает True тогда и только тогда, когда это целое число является простым. Ну, я написал is_prime функцию:

def is_prime(n): 
    n = abs(n) 
    i = 2 
    while i < n: 
     if n % i == 0: 
      return False 
     i += 1 
    return True 

, но это работает для п == 0, за исключением. Как я могу исправить это, чтобы заставить его работать для каждого целого? Я пытаюсь найти ответы как для того, чтобы написать функцию, чтобы получить сумму первых n простых чисел, так и как изменить мою функцию is_prime, которая должна работать на все возможные входные данные, а не только на положительные числа.

Answer 1

Почему не просто жесткий код ответа для i = 0 или 1?

n = abs(n) 
i = 2 
if(n == 0 || n == 1) 
    return true //Or whatever you feel 0 or 1 should return. 
while i < n: 
    if n % i == 0: 
     return False 
    i += 1 
return True 

И вы могли бы дополнительно улучшить скорость своего алгоритма, опуская некоторые цифры. Этот скрипт проверяет только до квадратного корня из n как . Никакое сложное число не имеет коэффициентов, больших его квадратного корня, если число имеет один или несколько факторов, один из них будет встречен перед квадратным корнем этого числа. При тестировании больших чисел это имеет большое значение.

n = abs(n) 
i = 2 
if(n == 0 || n == 1) 
    return true //Or whatever you feel 0 or 1 should return. 
while i <= sqrt(n): 
    if n % i == 0: 
     return False 
    i += 1 
return True 

Answer 2

Хорошо, что происходит, когда n равно 0 или 1?

Вы

i = 2 
while i < n: #is 2 less than 0 (or 1?) 
    ... 
return True 

Если вы хотите п 0 или 1, чтобы вернуться False, то не это, что вам нужно изменить ваш условный (или сама функция) для учета этих случаев?

Answer 3

В заявлении о своей проблеме говорится, что n является положительным целым числом. Итак, assert(n>0) и убедитесь, что ваша внешняя петля программы никогда не будет is_prime() с отрицательным значением или нолем.

Ваш алгоритм - опытное разделение каждого последующего нечетного число (лишняя будет большой скорости для вас) - работает, но будет очень медленным. Посмотрите на prime sieve для вдохновения.

Answer 4

попробовать это:

if(n==0) 
    return true 
else 
    n = abs(n) 
    i = 2 
    while i < n: 
     if n % i == 0: 
      return False 
     i += 1 
    return True 

Answer 5

Ваше задание заключается в следующем.

Предположим, что имеется функция is_prime. Предположим, что переменная n была связана с положительным целым числом. Напишите операторы, необходимые для вычисления суммы первых n простых чисел. Сумма должна быть связана с общей суммой переменных.

Как NVRAM справедливо указывает в комментариях (и никто другой не кажется, что взял на), вопрос состояния «предполагают наличие функции is_prime».

У вас нет есть, чтобы написать эту функцию. То, что вы делаете do, - это «написать операторы, необходимые для вычисления суммы первых n простых чисел».

псевдокод для этого было бы что-то вроде:

primes_left = n 
curr_num = 2 
curr_sum = 0 
while primes_left > 0: 
    if is_prime(curr_num): 
     curr_sum = curr_sum + curr_num 
     primes_left = primes_left - 1 
    curr_num = curr_num + 1 
print "Sum of first " + n + " primes is " + curr_sum 

Я думаю, вы обнаружите, что, если вы просто реализовать этот псевдокод в вашем языке выбора, это будет все, что вам нужно сделать.

Если вы ищете реализацию is_prime, чтобы проверить ваше задание, на самом деле не имеет значения, насколько она эффективна, так как вы будете тестировать только несколько небольших значений. Вам также не нужно беспокоиться о числах меньше двух, учитывая ограничения кода, который будет его использовать. Нечто подобное вполне приемлемо:

def is_prime(num): 
    if num < 2: 
     return false 
    if num == 2: 
     return true 
    divisor = 2 
    while divisor * divisor <= num: 
     if num % divisor == 0: 
      return false 
     divisor = divisor + 1 
    return true