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

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

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

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

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

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

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

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

Задача про простые числа. Выпишите все простые числа, находящиеся в интервале между а и б - C++
#include <stdio.h> #include <iostream> #include <conio.h> #include <math.h> using std::cout; using std::cin; using...

Задача на простые числа - C++
Определить все числа, принадлежат промежутку , сумма цифр которых простым числом.

Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа - C++
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа. Простые числа это когда они делятся только...

Задача про числа - C++
Думаю, думаю, но всё равно не могу понять как решить. Задача: Дан массив из положительных чисел и два числа a и b. Мы можем отнять...

Задача про автоморфные числа - C++
Помогите пожалуйста с кодом. Необходимо написать программу, которая будет выдавать желаемое количество автоморфных чисел. Код написал, но...

Задача про комплексные числа(закрытые переменные) - C++
Нужна срочно ваша помощь, помогите не смыслящему человеку:cry:, модифицировать программу таким образом, чтобы класс содержал закрытые...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Vourhey
Почетный модератор
6478 / 2253 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
01.10.2009, 18:45 #2
Мы поможем. В чем помощь нужна?
M128K145
Эксперт С++
8286 / 3505 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
01.10.2009, 19:13 #3
Цитата Сообщение от SaiLask Посмотреть сообщение
Сделать отчет, в котором будет замерено время работы оптимизированной и неоптимизированной версий программ для n >= 500000.
Неоптимизированная - это специально придуманный велосипед с 99.9% кода которого ничего не делают, а тянут немеряно ресурсов? Или что?
Nick Alte
Эксперт С++
1636 / 1008 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
01.10.2009, 19:50 #4
Неоптимизированная - это тупое решение задачи "в лоб". Например, перебор в качестве кандидатур в простые числа всех чисел от 2 до N. Перебор только нечётных чисел сократит время работы сразу в 2 раза. Создание списка уже найденных простых чисел способно очень основательно ускорить проверку на простоту. Использование более хитрых методов (вроде малой теоремы Ферма) сделает проверку на простоту просто-таки молниеносной.
novi4ok
551 / 504 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
01.10.2009, 20:17 #5
максимальное "н" известно? или может быть и 100000000000000000000000000000000000000000000000000000000000, например?
odip
Эксперт С++
7157 / 3297 / 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, например?
максимальное "н" неизвестно
для любого хотя бы дайте!

odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 23:19 #8
для любого хотя бы дайте!
Ссылку тебе уже дали - сходи посмотри.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.10.2009, 23:19
Привет! Вот еще темы с ответами:

Даны целые числа р и q. Получить все делители числа q, взаимно простые с р. - C++
Даны целые числа р и q. Получить все делители числа q, взаимно простые с р. Решите на С++. Заранее спасибо!

Даны натуральные числа a,b(a<= Ь). Получить все простые числа р, удовлетворяющие неравенствам a<= р<= b. - C++
Даны натуральные числа a,b(a&lt;= Ь). Получить все простые числа р, удовлетворяющие неравенствам a&lt;= р&lt;= b. Решите на С++. Буду очень...

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p. - C++
Даны натуральные числа p и q. Получить все делители числа q , взаимно простые к p.

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p - C++
Даны натуральные числа p и q. Получить все делители числа q , взаимно простые к p. помогите сделать на с++


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.10.2009, 23:19
Ответ Создать тему
Опции темы

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