С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.88
Venoblast
0 / 0 / 0
Регистрация: 16.01.2009
Сообщений: 8
#1

Вывести все простые числа от M до N включительно - C++

20.01.2009, 16:38. Просмотров 9437. Ответов 5
Метки нет (Все метки)

Ребят, как можно сократить время выполнения этой задачи.
Необходимо вывести все простые числа от M до N включительно.
В выходной файл OUTPUT.TXT выведите в одной строке через пробел все простые числа от M до N в порядке возрастания. Если таковых чисел нет, то следует вывести «Absent».

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <fstream>
 
int simple(int n)
{  
    for(int i=2;i<=n/2;i++)
        if( (n%i)==0 )
            return 0;  
    return 1;  
}  
 
int main()
{
    using namespace std;
    ifstream finp("input.txt");
    ofstream fout("output.txt");
    int a,b,c=0;
    finp>>a>>b;
    
    for (int i=a;i<=b;i++)
    {
        if( simple(i)==1 )
        {
            fout<<i<<" ";
        }
    }
    if (c==0);
    {
        fout<<"Absent";
    }
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.01.2009, 16:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вывести все простые числа от M до N включительно (C++):

Вывести все простые числа от M до N включительно - C++
Вывести все простые числа от M до N включительно. Ввод В первой строке находятся разделённые пробелом M и N. Вывод Вывести числа...

Цикл: Вывести все простые числа от M до N включительно - C++
Вывести все простые числа от M до N включительно. Вывести числа в порядке возрастания, по одному в строке. Если между M и N включительно...

Вывести все простые числа, меньшие заданного n, включительно - C++
Простое число Помогите Пожалуйста! Простое число это число которое делится только на 1 и на самого себя. Пользователь...

Решето Эратосфена: найти все простые числа в интервале от A до B включительно - C++
По введённым числам A и B вывести все простые числа в интервале от A до B включительно. Входные данные В единственной строке вводятся...

Вывести все числа от n1 до n2 включительно - C++
Задание 3 Принять с клавиатуры 2 натуральных числа n1 и n2. Выведите все числа от n1 до n2 включительно, в порядке возрастания, если n1 &lt;...

Вывести все целые числа от A до B включительно - C++
Даны целые положительные числа A и B (A &lt; B). Вывести все целые числа от A до B включительно; при этом каждое число должно выводиться ...

5
maximus09
32 / 32 / 3
Регистрация: 29.12.2008
Сообщений: 75
20.01.2009, 20:53 #2
Можно по-другому реализовать функцию проверки числа на предмет, является ли оно простым.

См. мое решение к третьей задачи по этой ссылке.
0
Venoblast
0 / 0 / 0
Регистрация: 16.01.2009
Сообщений: 8
21.01.2009, 23:42  [ТС] #3
нет, все равно время выполнения задачи превышает 1 сек,

проблема в проверки на "Absent"

то есть, если в указанном промежутке от m до n, нет простых чисел нужно вывести сообщение "Absent".

Как это реализовать по быстрому?
0
maximus09
32 / 32 / 3
Регистрация: 29.12.2008
Сообщений: 75
23.01.2009, 18:00 #4
А если попробовать воспользоваться той же гипотезой Гольдбаха. Хоть она и не доказана строго, но все же проверена для большого количества чисел.

Говоря иными словами, для любого четного числа N, существует пара простых чисел, одно из которых меньше (или равно) N/2, а другое - больше или равно (в противном случае сумма этих двух чисел никогда не станет равной N).

Если хорошенько поразмыслить, то можно этот факт использовать для сужения диапазона поиска.

Добавлено через 21 час 38 минут 31 секунду
Также можно сделать так, чтобы в переборе всех чисел от m до n участвовали только нечетные числа (т.к. четные числа, за исключением 2) заведомо не являются простыми.
0
Liraim
6 / 6 / 0
Регистрация: 28.01.2009
Сообщений: 15
28.01.2009, 15:04 #5
Есть смысл проверять делимость до корня из n, если я не ошибаюсь, тогда число n является простым, только надо сделать так чтобы он 1 раз вычислял корень.

Если еще сократить время выполнения, то корень можно вычислить корень из N и записать в переменную, и проверять на делимость до него.
0
xToTa
13 / 13 / 0
Регистрация: 26.01.2009
Сообщений: 162
28.01.2009, 15:31 #6
А я если чесно не пойму суть строк
C++
1
2
3
4
 if (c==0);  
     {  
         fout<<"Absent";  
     }
у тебя "с" в начале инициализируется нулем и нигде не меняется, если я не ошибаюсь, так в чем тогда проверка ?
0
28.01.2009, 15:31
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.01.2009, 15:31
Привет! Вот еще темы с ответами:

Рекурсия: вывести все числа от A до B включительно - C++
Нужна помощь Даны два целых числа A и В (каждое в отдельной строке). Вывести все числа от A до B включительно, в порядке возрастания,...

Вывести все целые числа от A до B включительно - C++
Даны целые положительные числа A и B (A &lt; B). Вывести все целые числа от A до B включительно; при этом каждое число должно выводиться ...

Вывести на печать все числа до нуля включительно - C++
Дана последовательность чисел, среди которых имеется 1 нуль. Вывести на печать все числа до нуля включительно.

Вывести на печать все числа до нуля включительно - C++
Одномерный массив. Дана задача: Дана последовательность чисел (рандомно), среди которых имеется один нуль (рандомно). Вывести на печать...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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