Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 32, средняя оценка - 4.91
SaiLask
0 / 0 / 0
Регистрация: 01.10.2009
Сообщений: 9
#1

Задача про простые числа. - C++

01.10.2009, 18:31. Просмотров 3885. Ответов 7
Метки нет (Все метки)

Привет!
кто может помогите мне с такой задачкой!

Необходимо написать программу, которая для заданного натурального числа n (вводится с клавиатуры после соответствующего запроса) найдет список всех простых чисел от 2 до n. Вывод списка простых чисел осуществляется на экран. Необходимо провести оптимизацию алгоритма решения задачи с целью повышения быстродействия написанной программы. Сделать отчет, в котором будет замерено время работы оптимизированной и неоптимизированной версий программ для n >= 500000.

Заранее спс!!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2009, 18:31     Задача про простые числа.
Посмотрите здесь:

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p. C++
C++ Даны целые числа р и q. Получить все делители числа q, взаимно простые с р
Даны целые числа р и q. Получить все делители числа q, взаимно простые с р. C++
C++ Даны натуральные числа a,b(a<= Ь). Получить все простые числа р, удовлетворяющие неравенствам a<= р<= b.
Задача на простые числа C++
C++ Дано натуральное число. Вывести на экран все простые числа до заданного числа.
Задача про комплексные числа(закрытые переменные) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vourhey
Почетный модератор
6474 / 2249 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
01.10.2009, 18:45     Задача про простые числа. #2
Мы поможем. В чем помощь нужна?
M128K145
Эксперт С++
8282 / 3501 / 143
Регистрация: 03.07.2009
Сообщений: 10,707
01.10.2009, 19:13     Задача про простые числа. #3
Цитата Сообщение от SaiLask Посмотреть сообщение
Сделать отчет, в котором будет замерено время работы оптимизированной и неоптимизированной версий программ для n >= 500000.
Неоптимизированная - это специально придуманный велосипед с 99.9% кода которого ничего не делают, а тянут немеряно ресурсов? Или что?
Nick Alte
Эксперт С++
1605 / 997 / 118
Регистрация: 27.09.2009
Сообщений: 1,923
Завершенные тесты: 1
01.10.2009, 19:50     Задача про простые числа. #4
Неоптимизированная - это тупое решение задачи "в лоб". Например, перебор в качестве кандидатур в простые числа всех чисел от 2 до N. Перебор только нечётных чисел сократит время работы сразу в 2 раза. Создание списка уже найденных простых чисел способно очень основательно ускорить проверку на простоту. Использование более хитрых методов (вроде малой теоремы Ферма) сделает проверку на простоту просто-таки молниеносной.
novi4ok
550 / 503 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
01.10.2009, 20:17     Задача про простые числа. #5
максимальное "н" известно? или может быть и 100000000000000000000000000000000000000000000000000000000000, например?
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
01.10.2009, 20:28     Задача про простые числа. #6
Быстрый алгоритм поиска простых чисел тут - Большая коллекция решенных задач
SaiLask
0 / 0 / 0
Регистрация: 01.10.2009
Сообщений: 9
02.10.2009, 19:22  [ТС]     Задача про простые числа. #7
Цитата Сообщение от novi4ok Посмотреть сообщение
максимальное "н" известно? или может быть и 100000000000000000000000000000000000000000000000000000000000, например?
максимальное "н" неизвестно
для любого хотя бы дайте!

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.10.2009, 23:19     Задача про простые числа.
Еще ссылки по теме:

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p C++
C++ Найти числа-близнецы: простые числа разность между которыми равна 2
Задача про простые числа. Выпишите все простые числа, находящиеся в интервале между а и б C++
Задача про автоморфные числа C++
Найти простые числа с суммой цифр меньше заданного числа C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 23:19     Задача про простые числа. #8
для любого хотя бы дайте!
Ссылку тебе уже дали - сходи посмотри.
Yandex
Объявления
02.10.2009, 23:19     Задача про простые числа.
Ответ Создать тему
Опции темы

Текущее время: 15:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru