Алгоритм нахождения простых чисел
Оптимизация алгоритма нахождения простых чисел
2 3 5 7 11 13 17 19 23 29 31… $250.000…
Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.
Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.
Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.
Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.
А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.
Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.
В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:
Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.
P.S.
Благодаря замечаниям получаем Листинг 7:
при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053
Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143
Источник
Вывести простые числа одномерного массива
Помогите, нужно вывести на экран простые числа одномерного массива. При вызове функции поиска простых чисел на экран выводятся только нули.
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Простые числа исходного одномерного массива
Поменять местами максимальный и минимальный элементы среди простых чисел исходного одномерного.
Вывести простые числа из массива
Всем привет, нужна помощь! Никак не могу написать код Задан массив, есть ли среди элементов.
Вывести простые числа из массива
Вообщем не пойму, почему не работает. Для определения простое ли число использовал эту программу .
Вывести на экран только простые числа из массива
Написать программу, которая выводит на экран только простые числа. Массив и его длина вводятся.
ValeryS, я поменяла код, но всё равно только нул выводятся на экран
запоминается не число а позиция в массиве
это нужно или сами числа?
Добавлено через 1 минуту
Вывести все простые числа из заданного пользователем массива
Задан линейный массив чисел N. N вводит пользователь. Вывести все простые числа массива.
Из одномерного массива целых чисел, содержащего один нулевой элемент, вывести все числа
Из одномерного массива целых чисел, содержащего один нулевой элемент, вывести все числа.
Есть ли среди элементов массива простые числа? Если да, то вывести номера этих элементов
Задан целочисленный массив размерности N. Есть ли среди элементов массива простые числа? Если да.
Есть ли среди элементов заданного массива простые числа? Если да, то вывести номера этих элементов
Задан целочисленный массив размерности N. Есть ли среди элементов массива простые числа? Если да.
Источник
Найти простые числа в массиве
Было дано найти простые числа в массиве. Можете объяснить зачем создавать цикл в цикле. Буду очень признателен!
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Найти в массиве простые числа и заменить нулями
требуется задать массив целых чисел, и удалить(ну или как я для себя упростила заменить нулями) все.
Найти в массиве простые числа и добавить в новый массив
Помогите, не работает код Пользователь вводит элементы массива, нужно узнать, есть ли простные.
Найти все простые числа в массиве и упорядочить их по возрастанию
Найти все простые числа в массиве и упорядочить их по возрастанию
В одномерном целочисленном массиве найти простые числа и вывести их номера.
1. В одномерном целочисленном массиве найти простые числа и вывести их номера. 2. В двухмерном.
С половиной, это ты махнул 
zss, с n=1 промашка вышла
Добавлено через 1 минуту
И логичнее, имхо, unsigned int.
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа.
Выделить простые числа в массиве
Добрый вечер, форумчане. Я написал программу, которая выделяет простые числа в массиве. Мой.
Отсортировать только простые числа в массиве
Я написала код поиска простых чисел, их сортировки. Но мне нужно чтобы сортировались и выводились.
Вывести на экран все простые числа в одномерном массиве
Вывести на экран все простые числа в одномерном массиве. Как поняла будет что то похожее на это.
Источник
Вывод на экран элементов массивов, которые являются простыми числами
Здравствуйте! Пишу сюда в последней надежде на помощь! Нужно сдать две лабы последние, а как их делать, совсем не знай. Пробовал по аналогии делать, получалась чушь.
Вот они:
1) Написать программу, которая считывает массив натуральных чисел из файла, имя которого вводится с клавиатуры, и выводит на экран те элементы, которые являются простыми числами.
2) Написать программу, которая формирует очередь целых чисел, вводимых с клавиатуры, и выводит элементы очереди на экран. Найти в этой очереди максимальный элемент и перенести его в начало очереди. Вывести полученную очередь на экран.
С++ только начал самостоятельно изучать, так как в институте непонятно объясняют, но до этих тем ещё не дошёл, поэтому и обратился к вам! Допуск к зачёту нужен все-таки.
| Комментарий модератора | ||
| ||
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Определить количество и сумму элементов массива, которые не являются простыми числами
Пусть задан массив натуральных чисел из n компонент. Определить количество и сумму его.
Найти количество тех элементов массива, которые не являются простыми числами
Найти количество тех элементов массива, которые не являются простыми числами, а также найти.
Найти сумму тех элементов массива, которые являются простыми числами
Дан массив натуральных чисел А(N), значения элементов которого лежат в диапазоне . Найти сумму тех.
Вывести на экран индексы тех элементов одномерного массива, которые являются простыми числами
Составьте программу вывода на экран индексов элементов одномерного массива b(n) значение которых.
Добавлено через 28 минут
1.
igorrr37, И на эту компилятор ругается. ( Хотя может я что то не то делаю. Пишет, что:
d:\dust\81\81.cpp(26) : error C2374: ‘i’ : redefinition; multiple initialization
d:\dust\ïðîãðàìì\81\81.cpp(20) : see declaration of ‘i’
и ссылается на эту вот строчку в обоих случаях:
for(int i=0;i 0
dihlofos, Спасибо! ) Помогло! Теперь я вообще без долгов! ) Осталось зачётную программу написать и вообще всё отлично будет!
Всех с наступающим и огромное спасибо за помощь! 🙂
Добавлено через 18 часов 39 минут
Оказывается это ещё не всё! Если не сложно, взгляните:
1. Написать программу заполнения одномерного массива случайными числами из заданного диапазона. Из полученного массива все положительные числа занести во второй массив, а все отрицательные-в третий. Каждый из полученных массивов упорядочить по возрастанию. Определить во втором масиве количество элементов являющихся степенью 2. Второй и третий массивы записать каждый в отдельный файл.
Я в примерах лабораторных работ нашёл как заполнить одномерный массив случайными числами из заданного диапазона, но дальше тёмный лес, глухие сосны.
Я бы и сам попробовал сделать, но скорость моего обучения намного ниже, чем скорость поступающих лаб.. ((( Рад буду любой помощи!
Добавлено через 20 часов 48 минут
Друзья, уже нашёл программу. На всякий случай выложу здесь.
Вывести на экран те компоненты файла, которые являются простыми числами
Помогите пожалуйстаааааа решить задачу в Visual Basic 6.0. Записать в файл N-первых нечетных.
Построить массив В из элементов массива А, которые являются простыми числами
Помогите! Составить программу формирования массива А из N случайных целых чисел, сделать возможным.
Сформировать массив В, из элементов массива А, которые являются простыми числами
Здраствуйте. Помогите подправить мой код. Условие задачи: Дан одномерный целочисленный массив А из.
Найти количество элементов массива, которые являются простыми числами
Здраствуйте. Решите пожалуйста задачки!Заранее благодарен. Задачка №1 Сформировать массив из.
Источник
Найти в массиве количество простых чисел
Дан массив целых положительных чисел Фб требуется найти в нем количество простых чисел и вывести его. Число является простым тогда и только тогда, когда имеет ровно 2 различных положительных делителя.
Входные данные:
В первой строке выводится целое число N — количество чисел в массиве А. В второй строке вводятся N целых положительных чисел -элементы массива А (от 2 до 10000).
Выходные данные:
Требуется вывести количество простых чисел в массиве А.
Помощь в написании контрольных, курсовых и дипломных работ здесь.
В массиве целых чисел найти количество простых чисел
Требуется определить массив целых чисел , заполнить его случайными числами или ввести его элементы.
Найти количество четных чисел в первом массиве и количество нечетных чисел во втором массиве
Даны два массива целых чисел А (15) и В (15). Найти количество четных чисел в первом массиве и.
Ввод чисел до 0. Найти количество простых чисел. Ошибка синтаксиса
Задание: Ввод чисел до 0. Найти количество простых чисел. Укажите где ошибка и подскажите как.
Найти количество совершенных и простых чисел в последовательности
Добрый вечер ,помогите пожалуйста программу написать,я не могу понять даже с чего начать, не могу.
Источник