Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Поиск простых чисел
СообщениеДобавлено: 24 май 2013, 15:45 
Не в сети
Начинающий
Зарегистрирован:
24 май 2013, 15:22
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
добрый день. в теме не в зуб нагой. специализация совсем другая, так что прошу не ругать, возможно вопрос глупый))
вообще нужно мне найти список простых чисел(про алгоритм решета знаю:-) )
вот такая идея пришла мне в голову.
предположим у меня есть начальный список простых чисел:
2,3
т.к. все не простые числа можно выразить как произведение простых, если я определю алгоритм выбора последовательности простых чисел из списка таким образом что произведение этих простых чисел будет равняться следующему не простому числу то я могу найти следующее простое число и добавить его в список, при этом я буду хранить список только простых чисел.
то есть алгоритм выглядит так:
S-список выбранных простых чисел на прошлом шаге
p1-прошлое не простое число
Fi(Z,S)-возвращает список простых чисел произведение которых равно следующему простому числу
инициализация:
p1=1// на данном этапе мне важно чтобы в p1 было значение
Z=[2]
S=[]
//шаг алгоритма
S=F(Z,S)
p2=перемножаем все числа из S//следующее не простое число
если p1!=p2-1 то добавляем в Z p2-1//мы перешагнули p2-1, т.к. F(Z,S) возвращает все числа перемножив которые я получаю следующее не простое то p2-1 - простое
p1=p2
вопрос вообщем то в следующем - возможно ли определить функцию F? у меня это не получилось

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск простых чисел
СообщениеДобавлено: 24 май 2013, 16:23 
Не в сети
Начинающий
Зарегистрирован:
24 май 2013, 15:22
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
вот первые несколько результатов функции F
Z[1] Z[1]
Z[1] Z[2]
Z[1] Z[1] Z[1]
Z[2] Z[2]
Z[1] Z[3]
Z[1] Z[1] Z[2]
Z[1] Z[4]
Z[2] Z[3]
Z[1] Z[1] Z[1] Z[1]
Z[1] Z[2] Z[2]
Z[1] Z[1] Z[3]
придумать функцию генератор немогу

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск простых чисел
СообщениеДобавлено: 24 май 2013, 17:18 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13534
Откуда: Москва
Cпасибо сказано: 1290
Спасибо получено:
3616 раз в 3175 сообщениях
Очков репутации: 678

Добавить очки репутацииУменьшить очки репутации
Не мучайте голову. Умные люди давно проблему решили.
Набирайте команду ifactor(A) и система (например, Maple) скажет Вам, число A простое или составное.

Если нужно распечатать все простые числа до 1000, то по проге

for A to 1000 do if isprime(A) = true then print(A); end if end do

через 5 секунд получите результат.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск простых чисел
СообщениеДобавлено: 24 май 2013, 18:51 
Не в сети
Начинающий
Зарегистрирован:
24 май 2013, 15:22
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
спасибо но не стоит задачи определить простое число или нет. есть вопрос - можно ли найти числа от 1 до n указанным выше способом.
Именно указанным. задача не практическая и имеет чисто академический интерес. пришла в голову идея, хочется узнать можно так или нет)))
и опять же а если я хочу не от 1 до n а от 1 до 2^256 к примеру. тогда у меня нет памяти просто чтобы хранить что-то кроме самих простых чисел.
вообщем чисто теоритический интерес, знаю что другие решения есть и хочу узнать только то можно ли решить так)))

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск простых чисел
СообщениеДобавлено: 24 май 2013, 20:15 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
stivsh писал(а):
Fi(Z,S)-возвращает список простых чисел произведение которых равно следующему простому числу
Хотел бы я посмотреть на простое число, равное произведению простых :shock:

Методом телепатии могу предположить, что ТС индуктивно генерит список составных чисел, удаляет его из списка всех натуральных и получает новый кусок списка простых чисел.
Т.е. тривиально. Решать можно как попало, только обычно хотят решать побыстрее.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск простых чисел
СообщениеДобавлено: 24 май 2013, 20:43 
Не в сети
Начинающий
Зарегистрирован:
24 май 2013, 15:22
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Sonic писал(а):
stivsh писал(а):
Fi(Z,S)-возвращает список простых чисел произведение которых равно следующему простому числу
Хотел бы я посмотреть на простое число, равное произведению простых :shock:

сори печатался.
Fi(Z,S)-возвращает список простых чисел произведение которых равно следующему НЕ простому числу
конечно же не получишь простое число произведением))
есть НЕ простое число p1 и следующее за ним НЕ простое число p2.
если p2-1 не равно p1 то p2-1 - простое.
то есть я предположил что можно написать такой генератор который из списка всех простых чисел по очереди выплёвывает все НЕ простые. если два числа идут не последовательно то между ними простое, добавляем его в список

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск простых чисел
СообщениеДобавлено: 25 май 2013, 06:29 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Не простое число кроме 1 называется составным.
И работать это все будет крайне медленно, а потому - никому это не нужно. Решето Эратосфена работает быстрее

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Поиск простых чисел
СообщениеДобавлено: 26 май 2013, 00:56 
Не в сети
Начинающий
Зарегистрирован:
24 май 2013, 15:22
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
для решета Эратосфена нужно хранить все числа а не только простые, скорость работы не возможно определить не определив F. решето Эрастофена работает не так уж и быстро))) для больших чисел(больше 2000 бит) не знаю другого способа кроме как выбрать на угад, проверить тестом Рабина-Миллера. кстати если кто знает способ быстро и на 100% проверить большое число на то является ли оно простым буду благодарен.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 8 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Множество простых чисел и пар простых чисел-близнецов бескон

в форуме Размышления по поводу и без

korolchukvasily

2

257

28 июн 2023, 11:23

Свойства простых чисел

в форуме Палата №6

Galina Alexandrovna

13

1569

21 июл 2016, 07:14

Формула для простых чисел

в форуме Размышления по поводу и без

Tirpa

30

1343

22 авг 2019, 23:30

Анализ простых чисел

в форуме Теория чисел

Nozdre

18

1149

20 май 2019, 23:01

Группы простых чисел

в форуме Теория чисел

vorvalm

5

1063

03 дек 2014, 15:00

Изучение простых чисел

в форуме Теория чисел

grubby

4

891

16 июн 2014, 16:59

Формула для простых чисел

в форуме Размышления по поводу и без

ammo77

1

241

31 янв 2020, 12:22

Формула простых чисел

в форуме Теория чисел

Xenobius

4

721

15 июл 2016, 08:01

Тройки простых чисел

в форуме Теория чисел

Claudia

5

591

18 июн 2018, 13:13

Формула простых чисел?

в форуме Теория чисел

Ferma

18

1087

05 дек 2018, 21:11


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 17


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved