Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Python → Генерація простих чисел та виявлення "близнюків"
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Доброго дня!
Підкажіть, будь ласка, як підступитися до наступної задачі:
Як можна генерувати прості числа із проміжку [n,2n]?
Дякую!
Знайшов такий код:
# t06_2
n =int(input('Введіть n '))
def isprime(n):
'''check if integer n is a prime'''
# make sure n is a positive integer
n = abs(int(n))
# 0 and 1 are not primes
if n < 2:
return False
# 2 is the only even prime number
if n == 2:
return True
# all other even numbers are not primes
if not n & 1:
return False
# range starts with 3 and only needs to go up the squareroot of n
# for all odd numbers
for x in range(3, int(n**0.5)+1, 2):
if n % x == 0:
return False
return TrueПоясніть, будь ласка, "псевдокод":
for i in range(n,2*n):
if prime(i):
passНе розумію - функція prime не існує.
prime - то функція, що перевіряє, чи число є простим
prime - то функція, що перевіряє, чи число є простим
А із якого модуля ця функія? Math пише, що не існує.
І що робить "pass"?
так то ж псевдокод. Pass, то типу - проходимо далі, по ідеї.
Пан 594202 під "прайм" мав на увазі будь-яку функцію, що перевіряє простоту числа - наприклад, ту, яку ви знайшли; а під "пас" - "паснути" число куди треба.
Ось тут є кілька методів: https://uk.wikipedia.org/wiki/Тест_простоти
Добре, подовжу допомагати
Зверніть увагу скільки мені довелось зробити змін щоб це запрацювало
Давайте перейдемо до наступної частини. Надіюсь це ваще згуглити і доведеться подумати
На рахунок пас, я мав на увазі якраз таки цей pass з ідеєю що туди треба щось дописати
Вийшов такий код:
n =int(input('Введіть n '))
my_list=[]
def isprime(n):
'''check if integer n is a prime'''
# make sure n is a positive integer
n = abs(int(n))
# 0 and 1 are not primes
if n < 2:
return False
# 2 is the only even prime number
if n == 2:
return True
# all other even numbers are not primes
if not n & 1:
return False
# range starts with 3 and only needs to go up the squareroot of n
# for all odd numbers
for x in range(3, int(n**0.5)+1, 2):
if n % x == 0:
return False
return True
for i in range(n,2*n):
if isprime(i):
my_list.append(i)
for i in range (1,len(my_list)):
if my_list[i]-my_list[i-1] == 2:
print(my_list[i-1],my_list[i])Як можна оптимізувати:
for i in range (1,len(my_list)):
if my_list[i]-my_list[i-1] == 2:
print(my_list[i-1],my_list[i])?
Дякую.
Оптимізувати за якою саме характеристикою? Пам'ять, час, довжина коду? Це не найгірший фрагмент у програмі, до речі.
Оптимізувати за якою саме характеристикою? Пам'ять, час, довжина коду? Це не найгірший фрагмент у програмі, до речі.
Я так розумію, що код має бути компактним, тому очікую, що є прийоми, які цей же фрагмент можуть скоротити. Якщо можете підказати що можна вдосконалити, також щодо простішої генерації простих чисел - буду вдячний.
І ще питання. Теоретично пишеться, що можна змінні не оголошувати. Як бути з
my_list=[]?
загугліть решето Ератосфена
Якщо користуватися саме цим базовим алгоритмом і скорочувати код, то
def is_prime(x):
return x>=2 and all(x%p!=0 for p in range(2,int(x**.5)+1))
n=int(input())
primes = [x for x in range(n,2*n+1) if is_prime(x)]
twins = [(a,b) for a,b in zip(primes,primes[1:]) if b-a==2]
print(twins)Якщо скорочувати час виконання (за рахунок пам'яті), то https://en.wikipedia.org/wiki/Sieve_of_Atkin
Якщо продовжувати оптимізувати базовий алгоритм, то можна:
- перевіряти лише числа, що мають вигляд 6*n±1, решта не прості;
- перевіряти, чи діляться вони лише на знайдені прості, а не на всі поспіль числа;
- замість кореня обчислювати квадрат поточного простого, щойно він стає більшим за число - перевірка завершена.
Дякую за код. Треба деякий час щоби осмислити, не скоро ).
Я правда, побачив по ходу в себе помилку, хоча вона не впливає:
for i in range(n,2*n):.
Правильно було б:
for i in range(n,2*n+1):2*n не може бути простим, так що все нормально.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися