1 Востаннє редагувалося DimONN (12.03.2018 23:04:08)

Тема: Генерація простих чисел та виявлення "близнюків"

Доброго дня!

Підкажіть, будь ласка, як підступитися до наступної задачі:
http://replace.org.ua/extensions/om_images/img/5aa6eaeadc9de/2.jpg

Як можна генерувати прості числа із проміжку [n,2n]?

Дякую!

2

Re: Генерація простих чисел та виявлення "близнюків"

Псевдокод
фор число ін рейндж(н, 2н):
    іф прайм(число):
        пас
Подякували: FakiNyan, koala2

3

Re: Генерація простих чисел та виявлення "близнюків"

Знайшов такий код:

# 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 не існує.

4

Re: Генерація простих чисел та виявлення "близнюків"

prime - то функція, що перевіряє, чи число є простим

5 Востаннє редагувалося DimONN (14.03.2018 23:40:29)

Re: Генерація простих чисел та виявлення "близнюків"

FakiNyan написав:

prime - то функція, що перевіряє, чи число є простим

А із якого модуля ця функія? Math пише, що не існує.

І що робить "pass"?

6

Re: Генерація простих чисел та виявлення "близнюків"

так то ж псевдокод. Pass, то типу - проходимо далі, по ідеї.

7

Re: Генерація простих чисел та виявлення "близнюків"

Пан 594202 під "прайм" мав на увазі будь-яку функцію, що перевіряє простоту числа - наприклад, ту, яку ви знайшли; а під "пас" - "паснути" число куди треба.

8

Re: Генерація простих чисел та виявлення "близнюків"

Ось тут є кілька методів: https://uk.wikipedia.org/wiki/Тест_простоти

9 Востаннє редагувалося 0x9111A (15.03.2018 10:41:37)

Re: Генерація простих чисел та виявлення "близнюків"

Добре, подовжу допомагати
Зверніть увагу скільки мені довелось зробити змін щоб це запрацювало

"генерація" простих чисел
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 isprime(i):
        print(i)

Давайте перейдемо до наступної частини. Надіюсь це ваще згуглити і доведеться подумати

На рахунок пас, я мав на увазі якраз таки цей pass з ідеєю що туди треба щось дописати

Подякували: DimONN, leofun012

10

Re: Генерація простих чисел та виявлення "близнюків"

Вийшов такий код:

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])

?
Дякую.

Подякували: 0x9111A1

11 Востаннє редагувалося koala (20.03.2018 10:44:40)

Re: Генерація простих чисел та виявлення "близнюків"

Оптимізувати за якою саме характеристикою? Пам'ять, час, довжина коду? Це не найгірший фрагмент у програмі, до речі.

12 Востаннє редагувалося DimONN (20.03.2018 11:12:37)

Re: Генерація простих чисел та виявлення "близнюків"

koala написав:

Оптимізувати за якою саме характеристикою? Пам'ять, час, довжина коду? Це не найгірший фрагмент у програмі, до речі.

Я так розумію, що код має бути компактним, тому очікую, що є прийоми, які цей же фрагмент можуть скоротити. Якщо можете підказати що можна вдосконалити, також щодо простішої генерації простих чисел - буду вдячний.

І ще питання. Теоретично пишеться, що можна змінні не оголошувати. Як бути з

my_list=[]

?

13

Re: Генерація простих чисел та виявлення "близнюків"

загугліть решето Ератосфена

14

Re: Генерація простих чисел та виявлення "близнюків"

Якщо користуватися саме цим базовим алгоритмом і скорочувати код, то

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, решта не прості;
- перевіряти, чи діляться вони лише на знайдені прості, а не на всі поспіль числа;
- замість кореня обчислювати квадрат поточного простого, щойно він стає більшим за число - перевірка завершена.

Подякували: leofun01, DimONN2

15

Re: Генерація простих чисел та виявлення "близнюків"

Дякую за код. Треба деякий час щоби осмислити, не скоро ).

Я правда, побачив по ходу в себе помилку, хоча вона не впливає:

for i in range(n,2*n):

.

Правильно було б:

for i in range(n,2*n+1):

16

Re: Генерація простих чисел та виявлення "близнюків"

2*n не може бути простим, так що все нормально.