Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 111, средняя оценка - 4.76
AndreyDemid
0 / 0 / 0
Регистрация: 08.12.2012
Сообщений: 3
#1

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

08.12.2012, 19:55. Просмотров 16005. Ответов 8
Метки нет (Все метки)

Для зачета задали написать программу для нахождения простых чисел от 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2012, 19:55
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл (C++):

Найти простые числа в заданном диапазоне с помощью решета Эратосфена
Задача: вывести простые числа в диапозоне от А до В. ( 2 ≤ А и ≤ В ≤ 100000...

Вывести простые числа от 1 до 1000000 с помощью решета Эратосфена
Вывести список простых чисел от 1 ого до млн.(1000000) с помощью решета...

Найти простые числа пользуясь методом решета Эратосфена НЕ используя массивы
Задача формулируется простыми словами: найти простые числа 0..N пользуясь...

Найти все простые числа в заданном диапазоне и вывести их на экран
Доброго времени суток! Есть задачка, есть кривое решение. :) Суть задачки...

Найти простые числа в заданном диапазоне (циклы)
Найти простые числа в диапазоне от 2 до 1000 цикл в цикле с помощью циклов for

Найти все простые числа в заданном диапазоне
Найти все простые числа в промежутке между натуральными числами а и b (а &gt;...

8
yekka
386 / 150 / 16
Регистрация: 12.05.2011
Сообщений: 450
08.12.2012, 20:15 #2
в файл записать можно
C++
1
ofstream os("filename");
и далее вместо cout << пишешь везде os <<

что значит "поставить таймер"?
1
AndreyDemid
0 / 0 / 0
Регистрация: 08.12.2012
Сообщений: 3
08.12.2012, 20:23  [ТС] #3
рассчитать сколько программа будет работать по времени
0
yekka
386 / 150 / 16
Регистрация: 12.05.2011
Сообщений: 450
08.12.2012, 20:27 #4
если тебе надо замерить время работы, то вот
http://www.cplusplus.com/reference/ctime/clock/
1
AndreyDemid
0 / 0 / 0
Регистрация: 08.12.2012
Сообщений: 3
08.12.2012, 20:31  [ТС] #5
спасибо
0
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++)
Объясните пожалуйста.
0
Байт
Эксперт C
17769 / 11794 / 2450
Регистрация: 24.12.2010
Сообщений: 23,716
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.
1
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,566
Записей в блоге: 1
08.09.2016, 16:26 #8
Файл ~500мег. У меня считает 20 сек, а пишет 2мин.
0
Konovaloff
0 / 0 / 0
Регистрация: 27.08.2016
Сообщений: 2
14.09.2016, 00:26 #9
Спасибо)
0
14.09.2016, 00:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.09.2016, 00:26
Привет! Вот еще темы с решениями:

Вывести все простые числа в заданном диапазоне, которые являются палиндромами
Напишите программу , которая выводит все простые числа , которые являются...

Вывести нечетные числа сгенерированные с помощью генератора псевдослучайных чисел в заданном диапазоне
С помощью генератора случайных чисел получить 30 целых чисел, лежащих в...

простые числа в заданном диапазоне
помогите пожалуйста написать программку...я все уже тут посмотрела, никак не...

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


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

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

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