Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
Массив простых чисел http://mathhelpplanet.com/viewtopic.php?f=44&t=65527 |
Страница 1 из 3 |
Автор: | pacha [ 30 май 2019, 19:36 ] |
Заголовок сообщения: | Массив простых чисел |
Как сформировать массив простых чисел? Какие есть алгоритмы? Длина массива задана. Есть мысль сравнить длину прохода от двух до случайно полученного числа. У простого она максимальна. |
Автор: | swan [ 30 май 2019, 20:36 ] |
Заголовок сообщения: | Re: Массив простых чисел |
Какого прохода? |
Автор: | slava_psk [ 31 май 2019, 08:25 ] |
Заголовок сообщения: | Re: Массив простых чисел |
Провести последовательные целочисленные деления от 2 до n (проверяемое число) и проверять остаток. |
Автор: | Emphatic18 [ 31 май 2019, 15:40 ] |
Заголовок сообщения: | Re: Массив простых чисел |
Если относительно просто то можно так program massiv результат Код: 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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 |
Автор: | Tantan [ 31 май 2019, 16:35 ] |
Заголовок сообщения: | Re: Массив простых чисел |
pacha писал(а): Какие есть алгоритмы? Длина массива задана. Решето Ератостена Вам известно? Если да, то : 1)задайте какого то большое [math]N >[/math] длину массива; 2) Через решето Ератостена найдите все простые чисель [math]\leqslant N[/math] и на кажды шаг следите достигли ли длину массива; 3.1) если достигли, то идите к концу алгоритма; 3.2) если не достигли длину массива, но достигли [math]N-1[/math], то увеличите горная граница цикла решето Ератостена на [math]= 2N[/math] и продолжайте от 2) дальше - [math]N+1,N+2,...,2N[/math] |
Автор: | vorvalm [ 31 май 2019, 18:12 ] |
Заголовок сообщения: | Re: Массив простых чисел |
Чтобы создать массив простых чисел до N, надо иметь массив простых чисел до [math]\sqrt N[/math] |
Автор: | atlakatl [ 31 май 2019, 18:50 ] |
Заголовок сообщения: | Re: Массив простых чисел |
pacha писал(а): сравнить длину прохода от двух до случайно полученного числа. У простого она максимальна. Простые числа статистикой не поборешь. В любом вероятностном алгоритме будут пропуски. Обычный алгоритм, видимо, и самый быстрый: 1. Есть два простых числа: 2 и 3 (первоначальный Х) . 2. Прибавляем к Х двойку. 3. Вычисляем квадратный корень из Х. Это ограничитель на последнее простое число, делимость на которое мы проверяем. 4. Делим Х на простые, начиная с 3 до корня из шага 3. 5. Если нулевой остаток получился, то немедленное прерывание: число составное. Переход к шагу 2. 6. Если нулевого остатка не случилось, то добавляем Х в наш массив. Переход к шагу 2. |
Автор: | Emphatic18 [ 01 июн 2019, 03:03 ] |
Заголовок сообщения: | Re: Массив простых чисел |
Если логическую функцию немного усложнить (как описал atlakatl), то получим приличное ускорение работы. В этом варианте определяем число на четность. Если оно четное, то сразу же говорим что оно не простое и остаток от деления перебором уже не ищем, для нечетных чисел цикл выполняется с шагом 2 начиная с попытки деления на 3. logical function f(x) массив первых 1000 простых чисел ▼ массив
atlakatl писал(а): 4. Делим Х на простые, начиная с 3 до корня из шага 3. Хотел только уточнить, именно на простые предлагаете делить? У меня просто с шагом 2. |
Автор: | atlakatl [ 01 июн 2019, 03:55 ] |
Заголовок сообщения: | Re: Массив простых чисел |
Emphatic18 писал(а): именно на простые предлагаете делить? Цэ ж основная теорема арифметики. Если число делится на 26, то оно делится и на 2, и на 13. Обратно, если число не делится ни на 2, ни на 13, то оно не делится на 26. Ну и проверять чётные числа незачем. Просто увеличиваем очередного кандидата на 2. |
Автор: | Emphatic18 [ 01 июн 2019, 04:40 ] |
Заголовок сообщения: | Re: Массив простых чисел |
Тогда вся программа получается такой: ▼ код
результат работы тот же но в этом случае функция применима только в этой основной программе |
Страница 1 из 3 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |