You have a few mistakes, most notably np is clearly meant to be the potential primes (it starts at n+1 which is the first potential number that fits your critera “the first prime number after the input number”), and yet you add x to your prime list, which is from range(2,199), you should be using:
isprime.append(j)
Your primality test is also the wrong way round as a result, you should be using:
j % x != 0
Lastly, you can’t append a number if that condition is true in one case, it has to be true in all cases (where x is an integer which satisfies 2 <= x < j), because of this you should switch your second set of for loops around (the x loop should be the inner loop), and you should also only loop up to j-1 (the number being tested). Additionally, you should instead choose to not add an item if j % x == 0:
for ...:
val_is_prime = True
for ...:
if j % x == 0:
val_is_prime = False
break
if val_is_prime:
isprime.append(j)
This results in the following code:
def prime(n):
np=[]
isprime=[]
for i in range (n+1,n+200):
np.append(i)
for j in np:
val_is_prime = True
for x in range(2,j-1):
if j % x == 0:
val_is_prime = False
break
if val_is_prime:
isprime.append(j)
return min(isprime)
And test run:
>>> prime(5)
7
>>> prime(13)
17
>>> prime(23)
29
Note that there’s several other efficiency improvements that could be made, but this answer focuses on the mistakes rather than improvements
У вас есть несколько ошибок, в первую очередь np явно предназначен для использования в качестве потенциальных простых чисел (он начинается с n+1которое является первым потенциальным числом, которое соответствует вашему критерию “первое простое число после входного числа”), и все же вы добавляетеx в ваш основной список, который из range(2,199), вы должны использовать:
isprime.append(j)
Ваш тест на простоту также неверен, поэтому вы должны использовать:
j % x != 0
Наконец, вы не можете добавить число, если это условие истинно в одном случае, оно должно быть истинным во всех случаях (где x – целое число, которое удовлетворяет2 <= x < j), поэтому вам следует переключить второй набор циклов for (x цикл должен быть внутренним циклом), и вы также должны выполнять цикл только до j-1(число проверяемых). Кроме того, вы должны вместо этого отказаться от добавления элемента, еслиj % x == 0:
for ...:
val_is_prime = True
for ...:
if j % x == 0:
val_is_prime = False
break
if val_is_prime:
isprime.append(j)
В результате получается следующий код:
def prime(n):
np=[]
isprime=[]
for i in range (n+1,n+200):
np.append(i)
for j in np:
val_is_prime = True
for x in range(2,j-1):
if j % x == 0:
val_is_prime = False
break
if val_is_prime:
isprime.append(j)
return min(isprime)
И тестовый запуск:
>>> prime(5)
7
>>> prime(13)
17
>>> prime(23)
29
Обратите внимание, что есть несколько других улучшений эффективности, которые можно сделать, но этот ответ фокусируется на ошибках, а не на улучшениях.
У задачи есть две стороны: математическая и технологическая. Математическую я предельно упростил – простота числа проверяется по определению. Можно сделать быстрее, но пока так.
Технологическая сторона. Я сделаю LowerPrime аналогом range. В Питоне range – неизменяемая последовательность. Из последовательности можно получить сколько угодно итераторов. Все итераторы полностью независимы. Демонстрация:
@>>> r = range(10) @>>> r range(0, 10) @>>> it = iter(r) @>>> it <range_iterator object at 0x7fc241c2b630> @>>> it2 = iter(r) @>>> it2 <range_iterator object at 0x7fc241c2a7f0>
Схема “одна последовательность – много итераторов” нужна чтобы работал код вроде:
r = range(10)
for n in r: # for вызывает iter(r) в начале
# что-то делаем
for n in r: # for вызывает iter(r) в начале
# что-то делаем
Без разных итераторов второй цикл не выполнится, так как первый исчерпал свой итератор полностью и нам нужен новый итератор.
Тоже самое для списка. Список один, итераторов много:
@>>> lst = [1, 2, 3] @>>> it = iter(lst) @>>> it <list_iterator object at 0x7fc241d12710> @>>> it2 = iter(lst) @>>> it2 <list_iterator object at 0x7fc241c781c0>
Становится ясно, что нужны два класса. Для списка убывающих простых LowerPrime, для итераторов LowerPrimeIter. Список простых заранее можно не составлять. Каждый вызов next продолжает поиск простых с того места, где итератор остановился раньше:
def is_prime(n):
return all(n % i != 0 for i in range(2, n))
class LowerPrime:
def __init__(self, number):
self._number = number
def __iter__(self):
return LowerPrimeIter(self._number)
class LowerPrimeIter:
def __init__(self, n):
self._n = n + 1
def __iter__(self):
return self
def __next__(self):
if self._n <= 2:
raise StopIteration
while True:
self._n -= 1
if is_prime(self._n):
return self._n
lower_prime = LowerPrime(number=11)
lower_prime_it = iter(lower_prime)
print('first', next(lower_prime_it))
for p in lower_prime_it:
print(p)
$ python lower_prime.py first 11 7 5 3 2
Другой вариант – SymPy. Это библиотека Python для символической математики. Он предоставляет несколько функций для прайма.
isprime(n) # Test if n is a prime number (True) or not (False).
primerange(a, b) # Generate a list of all prime numbers in the range [a, b).
randprime(a, b) # Return a random prime number in the range [a, b).
primepi(n) # Return the number of prime numbers less than or equal to n.
prime(nth) # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n.
prevprime(n, ith=1) # Return the largest prime smaller than n
nextprime(n) # Return the ith prime greater than n
sieve.primerange(a, b) # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes.
Вот несколько примеров.
>>> import sympy
>>>
>>> sympy.isprime(5)
True
>>> list(sympy.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> sympy.randprime(0, 100)
83
>>> sympy.randprime(0, 100)
41
>>> sympy.prime(3)
5
>>> sympy.prevprime(50)
47
>>> sympy.nextprime(50)
53
>>> list(sympy.sieve.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
person
SparkAndShine
schedule
24.02.2017
Формулировка задачи:
Дано простое число.Создать функцию, которая находит следующее за ним простое число. на языке питон
Код к задаче: «Python: Создать функцию, которая находит следующее простое число»
textual
var
n: integer;
function IsPrime(x: integer): boolean;
var
i: integer;
begin
IsPrime := true;
for i := 2 to Round(Sqrt(x)) do
if x mod i = 0 then
IsPrime := false;
end;
function NextPrime(x: integer): integer;
begin
if not IsPrime(x) then
exit
else
begin
repeat
Inc(x);
until IsPrime(x);
NextPrime := x;
end
end;
begin
repeat
Write('Введите простое число: ');
Readln(n);
until IsPrime(n);
Writeln('Следующее простое = ', NextPrime(n));
Readln
end.
Полезно ли:
5 голосов , оценка 3.800 из 5
