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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.79
tontb
0 / 0 / 0
Регистрация: 19.10.2010
Сообщений: 9
#1

Найти все простые числа, не превышающие число n, используя решето Эратосфена - C++

19.10.2010, 23:37. Просмотров 3979. Ответов 5
Метки нет (Все метки)

Дано натуральное число n (n>=2). Найти все простые числа, не превышающие число n, используя решето Эратосфена. Решетом Эратосфена называется следующий метод. Выпишем подряд все целые числа от 2 до n. Первым простым числом является число 2. Подчеркнем его, а все больше него числа, кратные числу 2, вычеркнем. Первым числом в ряду чисел, которые остались, является число 3. Подчеркнем его как простое число, а все больше него числа, кратные числу 3, вычеркнем. Первым числом среди оставшихся есть число 5, поскольку 4 уже зачеркнуто. Подчеркнем его как простое число, а все больше него числа, кратные числу 5, вычеркнем и т.д.

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

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

Простые числа. Решето Эратосфена - C++
Здравствуйте! Нужна ваша помощь, не могу понять условие этой задачи: Даны натуральное число n, целые числа a1,.....,an. Рассмотреть...

Решето Эратосфена. По номеру простого числа найти это число - C++
Найти n-ое по счёту простое число. Пример: 1 2 3 4 5 6 7 8 9 10 11 Из них простые 1 2 3 5 7 11 порядковые номера 123456 ...

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

Получить все простые числа не превышающие значения n - C++
Дано натуральное число n (n<=100). Получить все простые числа, которые не превышают это значение. Для ускорения вычислений при проверки...

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

5
dihlofos
Бродяга
303 / 257 / 17
Регистрация: 27.08.2010
Сообщений: 553
20.10.2010, 07:53 #2
Писал похожую штуку когда-то. Выводит простые числа до 999.
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
#include <iostream.h>
 
int main()
{
const int SIZE = 1000;
int array[SIZE], i, j;
 
for (i = 0; i < SIZE; i++)
    array[i]=i;       // заполнение массива цифрами от 0 до SIZE-1
 
// заменим все не простые числа нулями:
for (i = 2; i < SIZE; i++) // начинаем просмотр с 2
{
   if (array[i]!=0)     
      for(j=i+1; j<SIZE; j++) // просмотр элементов>i-го
      {
         if (array[j]%array[i]==0)
            array[j]=0;// если элемент кратен i-му, то обнуляем этот элемент
      }
}
 
// вывод простых чисел:
for (i = 2; i < SIZE; i++)
   if (array[i]!=0)
      cout<<array[i]<<'\t';
 
cin.get();
return 0;
}
1
st_dent
64 / 64 / 3
Регистрация: 05.07.2010
Сообщений: 219
20.10.2010, 14:43 #3
Ещё вариант:
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*Дано натуральное число n (n>=2). Найти все простые числа, не превышающие число n, используя решето Эратосфена. 
Решетом Эратосфена называется следующий метод. Выпишем подряд все целые числа от 2 до n. 
Первым простым числом является число 2. Подчеркнем его, а все больше него числа, кратные числу 2, вычеркнем. 
Первым числом в ряду чисел, которые остались, является число 3. 
Подчеркнем его как простое число, а все больше него числа, кратные числу 3, вычеркнем. 
Первым числом среди оставшихся есть число 5, поскольку 4 уже зачеркнуто. 
Подчеркнем его как простое число, а все больше него числа, кратные числу 5, вычеркнем и т.д.
*/ 
 
#include <iostream>
 
#define   stop __asm nop
using namespace std;
 
int main()
{
    int n,count=0,el=2;
    cin>>n;
    int*ar=new int [n-1];
    
    //заполним массив от 2 до n
    for(int i=0;i<n-1;++i)
    {ar[i]=el++;}
    
    //Найдем все простые числа, не превышающие число n, используя решето Эратосфена.
    for (int i=0;i<n-1;++i)
       {
           for (int j=i+1;j<n;++j)
           {
               if(ar[i]==0)
               {
                   count++;
                   break;
               }
               else if(j<n-1&&ar[j]%ar[i]==0)
               {
                   ar[j]=0;
               }
            }
       }
    
    //перенесем все найденные числа в новый массив и распечатаем их
    int j=0;
    int*tmp=new int[n-1-count];
    for (int i=0;i<n-1-count;++i)
       {
           while(j<n-1)
           {
               if(ar[j]){tmp[i]=ar[j];++j;break;}
               ++j;
           }
           cout<<tmp[i]<<" ";
       }
    
    delete[]tmp;
    delete[]ar;
    ar=0;tmp=0;
stop
    return 0;
}
1
tontb
0 / 0 / 0
Регистрация: 19.10.2010
Сообщений: 9
20.10.2010, 15:55  [ТС] #4
спасибо за помощь!)
0
Ksen111
0 / 0 / 0
Регистрация: 07.12.2015
Сообщений: 9
12.09.2016, 15:49 #5
подскажите, а как сделать, чтобы функция находила все простые числа методом эратосфена?
0
zer0mail
2379 / 2010 / 200
Регистрация: 03.07.2012
Сообщений: 7,251
Записей в блоге: 1
12.09.2016, 22:02 #6
Цитата Сообщение от Ksen111 Посмотреть сообщение
подскажите, а как сделать, чтобы функция находила все простые числа методом эратосфена?
Что значит "все простые"? Простых чисел бесконечно много
0
12.09.2016, 22:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.09.2016, 22:02
Привет! Вот еще темы с ответами:

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

Найти все простые числа из интервала от 100 до 1000, используя логическую функцию - C++
Нужно написать программу, буду премного благодарен) Знаю, что на самом деле тут всё просто, но я только начал учиться и пока не совсем...

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

Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа - C++
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа. Простые числа это когда они делятся только...


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

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

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