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

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

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

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

20.01.2009, 16:38. Просмотров 9039. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.01.2009, 16:38     Вывести все простые числа от M до N включительно
Посмотрите здесь:

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

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

Решето Эратосфена: найти все простые числа в интервале от 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 включительно; при этом каждое число должно выводиться ...

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

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

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

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

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

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

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

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

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

Если еще сократить время выполнения, то корень можно вычислить корень из N и записать в переменную, и проверять на делимость до него.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.01.2009, 15:31     Вывести все простые числа от M до N включительно
Еще ссылки по теме:

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

Циклы: вывести все числа от 0 до 100 включительно - C++
Как вывести все числа от 0 до 100 включительно?? Просто делаю программу которая выглядит в виде загрузки. Типо : loading...0 ...

Вывести все целые числа от 0 до 255 включительно - C++
используя только одну переменную типа usingned char, только один оператор цикла, создать цикл в теле которого выводятся все целые числа от...

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

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

Вывести все четные числа, кратные пяти, в интервале от 2 до 100 включительно - C++
Составить блок-схему алгоритма и программу согласно зада- нию. Вывести все четные числа кратные пяти в интервале от 2 до 100 вклю- ...


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

Или воспользуйтесь поиском по форуму:
xToTa
13 / 13 / 0
Регистрация: 26.01.2009
Сообщений: 162
28.01.2009, 15:31     Вывести все простые числа от M до N включительно #6
А я если чесно не пойму суть строк
C++
1
2
3
4
 if (c==0);  
     {  
         fout<<"Absent";  
     }
у тебя "с" в начале инициализируется нулем и нигде не меняется, если я не ошибаюсь, так в чем тогда проверка ?
Yandex
Объявления
28.01.2009, 15:31     Вывести все простые числа от M до N включительно
Ответ Создать тему
Опции темы

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