Расчет простых чисел

Question

Я сейчас занимаюсь в MIT opencourse, и уже второе задание, я чувствую, что оно оставило меня в дураках.http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset1a.pdf

Специфика этого - написать что-то, что может вычислить 1000-е простое число.Мы знаем только о командах print, ==, =, 1 =, если, иначе, elif, while,%, -, +, *, /, я думаю.Мы также еще не знаем об импорте библиотек.

Моя идея о том, как это будет работать, - взять нечетное число и попытаться разделить его на 3,4,5,6,7,8,9и если% n! = 0, то добавьте число в переменную NumberofPrimes, начиная с 11 в качестве базы тестов, и присваивая ему базовое значение 4 в основе NumberofPrimes, хотя я не знаю, верно ли это, потому что я не знаю, как отобразить 1000-е простое число.

Я близок?

Последнее его воплощение выглядит следующим образом:

##calculate the 1000th prime number
potprime = 3
numberofprime = 1
cycle = if potprime%3 = 0:
            break
        if potpimre%4 = 0:
            break
        if potprime%5 = 0:
            break
        if potprime%6 = 0:
            break
        if potprime%7 = 0:
            break
        if potprime%8 = 0:
            break
        if potprime%9 = 0:
            break
        numberofprime + 1
        potprime + 1

if potprime%2 == 0:
    potprime = potprime + 1
if potprime != 0:
    cycle

Гдеточно я иду не так?Проведи меня через это шаг за шагом.Я действительно хочу научиться этому, хотя чувствую, что меня здесь просто не пускают.

В этот момент для меня было бы более полезно увидеть, как можно сделать правильный, чемделая это.Я работал 3 часа и никуда не попал.Если у кого-то есть решение, я был бы более чем рад взглянуть на него и попытаться извлечь уроки из этого.

Answer 1

Похоже, я опоздал

Совершенно очевидно, что если число не делится ни на одно простое число, то это число само является простым числом. Вы можете использовать этот факт, чтобы минимизировать количество делений.

Для этого вам нужно вести список простых чисел. И для каждого числа только попробуйте делить с простыми числами уже в списке. Для дальнейшей его оптимизации вы можете отбросить все простые числа, превышающие квадратный корень из числа проверяемого. Для этого вам нужно будет импортировать функцию sqrt ().

Например, если вы тестируете на 1001, попробуйте протестировать с 3, 5, 7, 11, 13, 17, 19, 23, 29 и 31. Этого должно быть достаточно. Также никогда не пытайтесь выяснить, является ли четное число простым. Таким образом, в основном, если вы проверяете нечетное число n, то после этого теста следующее число: (n + 2)

Протестировал приведенный ниже код. 1000-е простое число - 7919. Не большое число !!

Код может быть таким:

from math import sqrt

primeList = [2]
num = 3
isPrime = 1

while len(primeList) < 1000:
    sqrtNum = sqrt(num)

    # test by dividing with only prime numbers
    for primeNumber in primeList:

        # skip testing with prime numbers greater than square root of number
        if num % primeNumber == 0:
            isPrime = 0
            break
        if primeNumber > sqrtNum:
            break

    if isPrime == 1:
        primeList.append(num)
    else:
        isPrime = 1

    #skip even numbers
    num += 2

# print 1000th prime number
print primeList[999]

Answer 2

Следующий код - gross , но, поскольку 1000 действительно является небольшим индексом, он решает вашу проблему за доли секунды (и использует только те примитивы, о которых вы должны знать):

primesFound = 0
number = 1

while primesFound < 1000:
    number = number + 1          # start from 2

    # test for primality
    divisor = 2
    numberIsPrime = True
    while divisor*divisor <= number:   # while divisor <= sqrt(number)
        if number % divisor == 0:
            numberIsPrime = False
            break
        divisor = divisor + 1

    # found one?
    if numberIsPrime:
        primesFound = primesFound + 1

print number

Вы можете проверить решение здесь .Теперь вы должны найти более эффективное решение, оптимизировать и, возможно, перейти к 1000000-му простому числу ...

Answer 3

Ваш код для этого ответа может быть сжат только до этого:

prime_count = 1
start_number = 2
number_to_check = 2
while prime_count <= 1000:
    result = number_to_check % start_number

    if result > 0:
        start_number +=1

    elif result == 0:
        if start_number == number_to_check:
            print (number_to_check)
            number_to_check +=1
            prime_count +=1
            start_number =2
        else:
            number_to_check +=1
            start_number = 2

Answer 4

Мне кажется, что вы прыгаете в глубокий конец после того, как решили, что детский бассейн слишком глубокий.Проектом простых чисел будет присвоение 2 или 3 в большинстве начинающих классов программирования сразу после того, как базовый синтаксис будет рассмотрен.Вместо того, чтобы помочь вам с алгоритмом (есть много хороших), я собираюсь предложить вам попытаться изучить синтаксис с python shell , прежде чем писать длинные программы, так как отладка строки прощечем отладка всей программы.Вот то, что вы написали так, что на самом деле будет работать:

count = 4
n = 10                        #I'm starting you at 10 because your method 
                              #says that 2, 3, 5, and 7 are not prime
d = [2, 3, 4, 5, 6, 7, 8, 9]  #a list containing the ints you were dividing by

def cycle(n):                 #This is how you define a function
    for i in d:               #i will be each value in the list d
        if not n%i:           #this is equal to if n%i == 0
            return 0          #not prime (well, according to this anyway)
    return 1                  #prime

while count < 1000:
    count += cycle(n)         #adds the return from cycle to count
    n += 1

print n - 1

Ответ по-прежнему неверен, потому что это не то, как проверить на простое число.Но знание небольшого синтаксиса, по крайней мере, даст вам этот неправильный ответ, что лучше, чем множество трассировок.

(Кроме того, я понимаю, что списки для циклов и функций не были в списке того, что вы говоритеты знаешь.)

Answer 5

Во-первых, я уверен, что в Python, если вы хотите иметь оператор if, который проверяет, является ли A = B, вам нужно использовать оператор ==, а не =.

С другой стороны, ваш алгоритм будет считать число 143 простым, хотя 143 = 11 * 13

Вам необходимо отслеживать все простые числа, которые вы уже вычислили, - добавьте их вмассив.Используйте этот массив, чтобы определить, простое ли новое число, которое вы тестируете.

Answer 6

Чтобы ответить на ваш следующий вопрос: «Как мне отслеживать все простые числа?

Один из способов сделать это - составить список.Когда вы проверяете число на предмет его простоты или нет, добавьте это число к primeList

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

>>> primeList
[11, 13, 17]

Answer 7

Я предложил это решение в своем интервью, но я не получил работу :( В нем примерно на 1/100 итераций меньше, чем в приведенном выше решении:

from math import *

MAX_IDX=1000
MAX_IDX-=1

num_iter=0

l_pirme_list=[3]
candidate=l_pirme_list[0]
prime_counter=1

while prime_counter < MAX_IDX: 
    candidate+=2
    #Cut the binary number in half. This is quite faster than sqrt()
    bin_candidate=format(candidate, "2b")
    max_prime_search=int(bin_candidate[:len(bin_candidate)/2+1],2)+1
    # max_prime_search=sqrt(candidate)+1

    candidate_is_prime=1
    for prime_item in l_pirme_list:
        num_iter+=1

        if candidate % prime_item==0:
            candidate_is_prime=0
            break

        elif prime_item > max_prime_search:
            candidate_is_prime=1
            break


    if candidate_is_prime:
        prime_counter+=1
        l_pirme_list.append(candidate)

l_pirme_list.insert(0,2)
print "number iterations=", num_iter
print l_pirme_list[MAX_IDX]

Answer 8

Я очень опоздал на это, но, возможно, мой ответ кому-нибудь пригодится. Я делаю тот же открытый курс в Массачусетском технологическом институте, и это решение я придумал Он возвращает правильное 1000-е простое и правильное 100-тысячное простое, а также различные другие промежуточные значения, которые я тестировал. Я думаю, что это правильное решение (не самое эффективное, я уверен, но рабочее решение, я думаю).

#Initialise some variables
candidate = 1 
prime_counter = 1 

while prime_counter < 1000: 
    test = 2 
    candidate = candidate + 2

    # While there is a remainder the number is potentially prime.
    while candidate%test > 0:
        test = test + 1

    # No remainder and test = candidate means candidate is prime.
    if candidate == test: 
        prime_counter = prime_counter + 1

print "The 1000th prime is: " + str(candidate)

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

"Из теории чисел есть симпатичный результат, который гласит, что при достаточно большом n произведение простых чисел, меньших n, меньше или равно e ^ n и что с ростом n это становится жесткой границей (то есть отношение произведения простых чисел к e ^ n становится близко к 1 с ростом n). Вычисление произведения большого числа простых чисел может привести к очень большому числу, что потенциально может вызвать проблемы с нашими вычислениями. (Мы будем говорить о том, как компьютеры имеют дело с числами немного позже в этом термине.) Таким образом, мы можем преобразовать произведение набора простых чисел в сумму логарифмов простых чисел, применяя логарифмы к обеим частям этой гипотезы. В этом случае приведенная выше гипотеза сводится к утверждению, что сумма логарифмы всех простых чисел, меньших чем n, меньше чем n, и что с ростом n отношение этой суммы к n приближается к 1. "

Вот мое решение. Я печатаю результат для каждого 1000-го простого числа до 10 000-го простого.

from math import *

#Initialise some variables
candidate = 1 
prime_counter = 1 
sum_logs = log(2)

while prime_counter < 10000: 
    test = 2 
    candidate = candidate + 2
    # While there is a remainder the number is potentially prime.
    while candidate%test > 0:
        test = test + 1
    # No remainder and test = candidate means candidate is prime.
    if candidate == test: 
        prime_counter = prime_counter + 1
    # If the number is prime add its log to the sum of logs.
        sum_logs = sum_logs + log(candidate)
    if prime_counter%1000 == 0:
        # For every 1000th prime print the result.
        print sum_logs," ",candidate," ",sum_logs/candidate
print "The 10000th prime is: " + str(candidate)

Приветствия

Адриан

Answer 9

Твоя математика подвела тебя. Простое число - это число, которое имеет 2 делителя: 1 и себя. Вы не проверяете числа на простоту.