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

Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 111, средняя оценка - 4.76
AndreyDemid
0 / 0 / 0
Регистрация: 08.12.2012
Сообщений: 3
08.12.2012, 19:55     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл #1
Для зачета задали написать программу для нахождения простых чисел от 1 до 1000000000 и вывод их в файл,чтобы программа делала все это меньше 5 минут,желательно с помощью решета Эратосфена.
Как записать в файл и можно ли поставить таймер?

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
32
33
34
35
#include "stdafx.h"
#include <iostream>
#include <new>
#include <locale>
 
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{setlocale(LC_CTYPE, "russian"); //установка русского языка в консоли
    int i, j,S; //индексы
        int N; //размер массива
        bool *mas; //объявляем массив типа bool
 
        cout << "Простые числа от 1 до N \n";
        cout << "Введите число N ";
        cin >> S;
        N=S+1;
        mas= new bool [N]; //динамически выделяем память под массив размером N
 
        for(i=1; i<=S; i++) mas[i]=true; //заполняем массив значением true;
        
        //Алгоритм "Решето Эратосфена"
        for(i=2; ((i*i)<=S); i++)
                if(mas[i])
                        for(j=(i*i); j<=S; j+=i)
                                if(mas[j]) mas[j]=false;
 
        //Вывод результата на экран
        for(i=1; i<=S; i++)
                if(mas[i]) cout << i << " ";
 
 
        system("pause");
        return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2012, 19:55     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл
Посмотрите здесь:

C++ простые числа в заданном диапазоне
Найти простые числа пользуясь методом решета Эратосфена НЕ используя массивы C++
Найти все простые числа в заданном диапазоне и вывести их на экран C++
C++ Найти простые числа в заданном диапазоне с помощью решета Эратосфена
Решето Эратосфена: найти все простые числа в интервале от A до B включительно C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
08.12.2012, 20:15     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл #2
в файл записать можно
C++
1
ofstream os("filename");
и далее вместо cout << пишешь везде os <<

что значит "поставить таймер"?
AndreyDemid
0 / 0 / 0
Регистрация: 08.12.2012
Сообщений: 3
08.12.2012, 20:23  [ТС]     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл #3
рассчитать сколько программа будет работать по времени
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
08.12.2012, 20:27     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл #4
если тебе надо замерить время работы, то вот
http://www.cplusplus.com/reference/ctime/clock/
AndreyDemid
0 / 0 / 0
Регистрация: 08.12.2012
Сообщений: 3
08.12.2012, 20:31  [ТС]     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл #5
спасибо
Konovaloff
0 / 0 / 0
Регистрация: 27.08.2016
Сообщений: 2
08.09.2016, 01:21     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл #6
А почему в 23 строчке условием выполнением цикла является произведение i, а не просто i?
C++
1
for(i=2; ((i*i)<=S); i++)
Объясните пожалуйста.
Байт
 Аватар для Байт
13993 / 8824 / 1231
Регистрация: 24.12.2010
Сообщений: 15,990
08.09.2016, 09:03     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл #7
Если у числа N есть множитель a, такой, что a*a > N, то множитель b = N/a будет удовлетворять условию b*b < N
Другими словами, если число N составное, то какой-нибудь множитель найдется до корня из N.
Если это не понятно, попробуйте поиграть составными числами.
Вот есть число 187 = 17*11. 17*17 > 187. Но 11*11 < 187. То есть мы определим, что число 187 составное не доходя 14.
zer0mail
2188 / 1871 / 187
Регистрация: 03.07.2012
Сообщений: 6,661
Записей в блоге: 1
08.09.2016, 16:26     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл #8
Файл ~500мег. У меня считает 20 сек, а пишет 2мин.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.09.2016, 00:26     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл
Еще ссылки по теме:

C++ Найти простые числа в заданном диапазоне (циклы)
Вывести все простые числа в заданном диапазоне, которые являются палиндромами C++
Найти все простые числа в заданном диапазоне C++

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

Или воспользуйтесь поиском по форуму:
Konovaloff
0 / 0 / 0
Регистрация: 27.08.2016
Сообщений: 2
14.09.2016, 00:26     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл #9
Спасибо)
Yandex
Объявления
14.09.2016, 00:26     Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл
Ответ Создать тему
Опции темы

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