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

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

Войти
Регистрация
Восстановить пароль
 
dinbo
0 / 0 / 0
Регистрация: 03.11.2016
Сообщений: 18
#1

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

03.11.2016, 23:44. Просмотров 472. Ответов 11
Метки нет (Все метки)

В этой задаче мы реализуем генератор простых чисел. Простыми называются положительные целые, не имеющие делителей кроме 1 и самого числа. Вы можете прочесть больше в википедии. Самые популярные для начинающих программистов алгоритмы - Решето Эратосфена и Перебор делителей. Вы можете найти подробности о них по этим ключевым словам.

Итак, давайте создадим список или массив простых чисел в порядке возрастания:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...]
И потом напечатаем те из них, которые соответствуют индексам заданным во входных данных.

Входные данные указывают в первой строке количество простых чисел которые нужно напечатать.
Вторая строка содержит интересующие нас индексы в массиве простых чисел. Они будут в диапазоне от 1 до 200000.
Ответ должен содержать простые числа соответствующие указанным позициям в массиве.

Внимание в этой задаче индексы массива начинаются с 1 а не с 0 - это для того чтобы легче было пользоваться (в целях проверки) готовыми списками простых чисел из интернета.

Пример:

входные данные:
4
7 1 199999 4

ответ:
17 2 2750131 7
решите пожалуйста, очень срочно нужно, п.с. решение должно соответствовать входным и выходным данным, заранее спасибо
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2016, 23:44
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Реализовать генератор простых чисел с использованием решета Эратосфена и перебора делителей (C++):

Число простых чисел от 1 до N методом решета Сундарама - C++
Не врубаюсь как сделать. Проект С++, использующий динамическую библиотеку MSVCRT.dll вместо обычной MSVCRT90.dll...

Игра на основе решета эратосфена - C++
Доброго времени суток, нужна ваша помощь в написании программы "Разработать программу по визуализации алгоритма решета Эратосфена....

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

Найти простые числа в заданном диапазоне с помощью решета Эратосфена - C++
Задача: вывести простые числа в диапозоне от А до В. ( 2 ≤ А и ≤ В ≤ 100000 ) Если таких чисел нет - вывести "Fol". Желательно с...

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

Объяснить работу программы (нахождение простых чисел, решето Эратосфена) - C++
Поясните как работает эта прога а именно : #include <iostream> #include <conio.h> using namespace std; int main() { ...

11
DUMP
73 / 47 / 11
Регистрация: 22.02.2015
Сообщений: 306
04.11.2016, 01:58 #2
Тупо в лоб , но ответ за O(1)
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
// Example program
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <stdio.h>
 
using namespace std;
 
const int MAXSZ = 300001*10;
int n;
bool mark[MAXSZ];
 
int main()
{
    scanf("%d",&n);
    for(long long i = 2; i <= MAXSZ-1; i++)
        if(!mark[i])
            for(long long j = i*i; j <= MAXSZ-1; j+= i)
                mark[j] = true;
                
    vector<long long> simple;
    for(long long i = 1; i <= MAXSZ-1; i++)
        if(!mark[i])
            simple.push_back(i);
            
    for(int i = 0, id; i < n; i++)
    {
        scanf("%d",&id);
        cout << simple[id]<< " ";
    }
    
}
0
dinbo
0 / 0 / 0
Регистрация: 03.11.2016
Сообщений: 18
04.11.2016, 16:04  [ТС] #3
спасибо большое, а можно без scanf , мы это не проходили в классе просто, очень прошу, заранее спасибо
0
DUMP
73 / 47 / 11
Регистрация: 22.02.2015
Сообщений: 306
04.11.2016, 18:12 #4
dinbo, ну так замени на то что проходили std::cin
0
dinbo
0 / 0 / 0
Регистрация: 03.11.2016
Сообщений: 18
04.11.2016, 18:28  [ТС] #5
cin>>what? просто я даже не знаю структуру сканфа, и как оно работает

Добавлено через 5 минут
а всё, кажется, поняла

Добавлено через 4 минуты
const int MAXSZ = 300001*10; а что зачем и зачем такое число?
0
gru74ik
Модератор
Эксперт CЭксперт С++
4361 / 1937 / 210
Регистрация: 20.02.2013
Сообщений: 5,142
Записей в блоге: 22
04.11.2016, 18:46 #6
dinbo, так ты по-нашему умеешь! А я в соседней теме пыжусь, на буржуйском тебе расписываю
0
dinbo
0 / 0 / 0
Регистрация: 03.11.2016
Сообщений: 18
04.11.2016, 20:34  [ТС] #7
ахаххаах

Добавлено через 19 секунд
const int MAXSZ = 300001*10; а что зачем и зачем такое число?

Добавлено через 1 час 44 минуты
gru74ik, const int MAXSZ = 300001*10; а что зачем и зачем такое число?
0
gru74ik
Модератор
Эксперт CЭксперт С++
4361 / 1937 / 210
Регистрация: 20.02.2013
Сообщений: 5,142
Записей в блоге: 22
04.11.2016, 21:14 #8
Цитата Сообщение от dinbo Посмотреть сообщение
gru74ik, const int MAXSZ = 300001*10; а что зачем и зачем такое число?
dinbo, я не знаю. Спроси автора кода, что он имел ввиду.
0
dinbo
0 / 0 / 0
Регистрация: 03.11.2016
Сообщений: 18
04.11.2016, 21:18  [ТС] #9
DUMP, const int MAXSZ = 300001*10; а что зачем и зачем такое число? иожешь написать без этого? попонятнее
0
gru74ik
Модератор
Эксперт CЭксперт С++
4361 / 1937 / 210
Регистрация: 20.02.2013
Сообщений: 5,142
Записей в блоге: 22
04.11.2016, 22:08 #10
dinbo, MAX - максимальный, SZ - size (размер). Так DUMP назвал константу, которая будет обозначать количество элементов массива типа bool:
C++
1
2
const int MAXSZ = 300001*10;
bool mark[MAXSZ]; // три миллиона и ещё одна "ячейка" для элементов типа bool
За каким лешим ему там умножение понадобилось, леший только и знает. Почему именно это число - одному Велесу ведомо.

Добавлено через 38 минут
 Комментарий модератора 
dinbo, прекрати дублировать темы. Это запрещено правилами форума.
И названия для тем подбирай осмысленные.
0
dinbo
0 / 0 / 0
Регистрация: 03.11.2016
Сообщений: 18
05.11.2016, 06:59  [ТС] #11
DUMP, можете решить не через вектор, а просто через массив

Добавлено через 8 часов 28 минут
gru74ik, if(!mark[i]) что это значит
0
gru74ik
Модератор
Эксперт CЭксперт С++
4361 / 1937 / 210
Регистрация: 20.02.2013
Сообщений: 5,142
Записей в блоге: 22
05.11.2016, 11:58 #12
dinbo, if - это условный оператор. В переводе с английского, как Вы знаете (а мы уже убедились, что Вы знаете), означает "если". Внутри круглых скобок оператора if всегда размещают условие. Условием может быть переменная, экземляр класса, выражение. Что бы там ни было, оно приводится к типу bool, то есть либо true (истина), либо false (ложь).

Восклицательный знак - это так называемый унарный оператор логического отрицания - он инвертирует результат. То есть, если условие в круглых скобках истинно, оно его инвертирует в ложное, и наоборот. Как в обычной речи отрицательная частица НЕ.

Далее (после восклицательного знака) следует запись, означающая i-й элемент массива. Массив у нас в данном примере типа bool, то есть хранит значения либо true, либо false, как уже говорилось. Значит берётся i-e значение этого самого массива и инвертируется: если там в этом элементе лежит false, то это значение благодаря отрицанию ! превратиться в true, а значит программа зайдёт в эту ветку и выполнится тело оператора if. В противном случае, этот блок кода будет пропущен и выполнение программы будет продолжено далее.

dinbo, это элементарные всё знания. Вы так и будете спрашивать любую мелочь. Есть замечательная книга под названием Язык программирования С++. Лекции и упражнения (2012, 6-е издание), автор - Стивен Прата. Почитайте, толку больше будет.
2
05.11.2016, 11:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2016, 11:58
Привет! Вот еще темы с ответами:

Определить количество простых чисел, меньших N, используя решето Эратосфена - C++
Дан код: #include &lt;iostream&gt; using namespace std; static const int N = 1000; int main() { int i, a; for (i = 2; i &lt; N; i++)...

Найти простые числа в заданном диапазоне с помощью решета Эратосфена и вывести их в файл - C++
Для зачета задали написать программу для нахождения простых чисел от 1 до 1000000000 и вывод их в файл,чтобы программа делала все это...

Алгоритм перебора разных комбинаций простых чисел - C++
Доброго времени суток! Решаю разнообразные задачки по программированию, попалась вот такая: Определим функцию P(n,k) следующим...

Генератор простых чисел - C++
Подскажите, пожалуйста, хороший алгоритм (желательно с реализацией) генерации простых чисел (от 512 бит). Текущий алгоритм работает...


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

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

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