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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.88
Venoblast
0 / 0 / 0
Регистрация: 16.01.2009
Сообщений: 8
20.01.2009, 16:38     Вывести все простые числа от M до N включительно #1
Ребят, как можно сократить время выполнения этой задачи.
Необходимо вывести все простые числа от 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 включительно
Посмотрите здесь:

C++ Вывести на печать все числа до нуля включительно
C++ Цикл: Вывести все простые числа от M до N включительно
C++ Вывести все целые числа от A до B включительно
Вывести на печать все числа до нуля включительно C++
C++ Дано натуральное число. Вывести на экран все простые числа до заданного числа.
C++ Вывести все целые числа от A до B включительно
Вывести все четные числа, кратные пяти, в интервале от 2 до 100 включительно C++
Решето Эратосфена: найти все простые числа в интервале от A до B включительно C++
C++ Рекурсия: вывести все числа от A до B включительно
C++ Циклы: вывести все числа от 0 до 100 включительно
Вывести все числа от n1 до n2 включительно C++
Вывести все целые числа от 0 до 255 включительно C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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 и записать в переменную, и проверять на делимость до него.
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 включительно
Ответ Создать тему
Опции темы

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