Нахождение n-го простого числа с использованием Python

Question

Когда я запускаю этот код, даже для простого подсчета до 10-го простого числа (вместо 1000) я получаю перекос / измученный вывод - все «не простые» названия для моей переменной is_composite, мой test_num дает мне простое и составные числа, и мой prime_count выключен

Некоторые ответы, которые разработчики разделили, используют функции и математический импорт - это то, что мы еще не рассмотрели. Я не пытаюсь получить наиболее эффективный ответ; Я просто пытаюсь написать работоспособный код на Python, чтобы понять основы цикличности.

---

  # test a prime by diving number by previous sequence of number(s) (% == 0).  Do this by
  # counting up from 1 all the way to 1000.

test_num = 2 #these are the numbers that are being tested for primality
is_composite = 'not prime' # will be counted by prime_count
prime_count = 0 #count the number of primes


while (prime_count<10): #counts number primes and make sures that loop stops after the 1000th prime (here: I am just running it to the tenth for quick testing)


 test_num = test_num + 1   # starts with two, tested for primality and counted if so
 x = test_num - 1  #denominator for prime equation

 while (x>2):   
  if test_num%(x) == 0:
   is_composite = 'not prime'
  else: 
   prime_count = prime_count + 1 
  x = x - 1 


  print is_composite
  print test_num
  print prime_count 

Answer 1

См. Советы, данные MIT для вашего задания. Я цитирую их ниже:

1. Инициализация некоторых переменных состояния

2. Генерация всех ( нечетных ) целых чисел> 1 в качестве кандидатов на простое число

3. Для каждого целого числа-кандидата проверьте, является ли оно простым

   3,1. Один простой способ сделать это - проверить, делит ли любое другое целое число> 1 кандидата с остатком 0. Для этого вы можете использовать модульная арифметика , например, выражение a% b возвращает остаток после деления целого числа a на целое число b.

   3,2. Вы можете подумать, какие целые числа нужно проверять как делители - конечно, вам не нужно выходить за пределы проверяемого кандидата, но как скоро вы можете прекратить проверять ?

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

5. Остановитесь, когда достигнете подходящего конечного состояния. При формулировке этого условия, не забывайте , что ваша программа не сгенерировала первого простого числа (2) .

Это может выглядеть так:

def primes(n):
    # /2029352/samyi-bystryi-sposob-perechislit-vse-prostye-chisla-nizhe-n#2029364
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

Answer 2

Прежде всего, из расплывчатого описания вашего алгоритма первичной проверки видно, что вы проверяете каждое число вплоть до числа, которое вы проверяете на простоту.Однако на самом деле вам нужно только проверить до квадратного корня из этого числа.Дальнейшая оптимизация будет состоять в том, чтобы убрать все четные числа, кроме двух (вы можете сделать это, увеличив на два по одному и протестировав 2 по отдельности), вы получите:перебирает числа от 2 и выше, проверяя, являются ли они простыми, и добавляет одно к вашему счетчику, если они есть.Когда вы достигаете 1000, останавливаетесь и выводите число, передаваемое функции isprime.

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

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

from math import sqrt

def isprime(test):
    if test == 2: return True
    if test < 2 or test % 2 == 0: return False
    return not any(test % i == 0 for i in range(3, int(sqrt(test)) + 1, 2))

test_num = 2
prime_count = 1

while (prime_count< 1000): 

 test_num = test_num + 1  

 if (isprime(test_num)):
     prime_count += 1

print test_num

Answer 3

Это код, который я написал для C ++. Но менталитет должен быть таким же.

// This code was written by Mert Ener
#include <time.h>
#include <vector>
#include <iostream>

private: System::Void button1_Click_1(System::Object^  sender, 
                                          System::EventArgs^  e) { 
    using namespace std;
    UInt64 cloc = clock();
    long m = 1;
    long k = long::Parse(textBox1->Text)-2;   // The text you entered 
    std::vector<long> p(1,2);                 //   for the nth prime
    for( long n = 0; n <= k; n++ ) {
        m += 2;
        for( long l = 1; l <= n; l++ ) {
            if (m % p[l] == 0) {
                m += 2;
                l=0;}}
        p.push_back(m);}
    textBox2->Text = p[k+1].ToString(); // The textbox for the result.
    MessageBox::Show("It took me " + (clock() - cloc).ToString() 
                     + " milliseconds to find your prime.");}

Answer 4

Этот код ниже генерирует список простых чисел до 1 миллиона. Используя этот список, вы можете проверить на простые числа <1 триллион достаточно быстрым способом. Это выполняется в довольно быстрое время для простых чисел из 10-12 цифр. </p>

import math
from itertools import islice
# number of primes below the square root of x
# works well when x is large (x > 20 and much larger)
numchecks = lambda x: int((math.sqrt(x))/(math.log(math.sqrt(x)) - 1.084)) + 1

primes = [2,3,5]
primes = primes + [x for x in range(7, 48, 2) if all((x%y for y in islice( primes, 1, int(math.sqrt(x)) )))]
primes = primes + [x for x in range(49, 2400, 2) if all((x%y for y in islice( primes, 1, numchecks(x) )))]
primes = primes + [x for x in range(2401, 1000000, 2) if all((x%y for y in islice( primes, 1, numchecks(x) )))]

Вы можете увеличить количество сохраненных простых чисел, расширив описанный выше процесс, но программа займет много времени (но только один раз).

В своем коде вы можете проверить, является ли 'test_num' простым, используя следующее ...

test_num = 23527631
if test_num<100:
    checks = int(math.sqrt(test_num))
else:
    checks = numchecks(test_num)

isPrime = all(test_num%x for x in islice(primes, 0, checks))
print 'The number is', 'prime' if isPrime else 'not prime'
print 'Tested in', checks, 'divisions'