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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.79
tontb
0 / 0 / 0
Регистрация: 19.10.2010
Сообщений: 9
19.10.2010, 23:37     Найти все простые числа, не превышающие число n, используя решето Эратосфена #1
Дано натуральное число n (n>=2). Найти все простые числа, не превышающие число n, используя решето Эратосфена. Решетом Эратосфена называется следующий метод. Выпишем подряд все целые числа от 2 до n. Первым простым числом является число 2. Подчеркнем его, а все больше него числа, кратные числу 2, вычеркнем. Первым числом в ряду чисел, которые остались, является число 3. Подчеркнем его как простое число, а все больше него числа, кратные числу 3, вычеркнем. Первым числом среди оставшихся есть число 5, поскольку 4 уже зачеркнуто. Подчеркнем его как простое число, а все больше него числа, кратные числу 5, вычеркнем и т.д.

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

Найти простые числа пользуясь методом решета Эратосфена НЕ используя массивы C++
C++ Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
Найти все простые числа из интервала от 100 до 1000, используя логическую функцию C++
Используя метод "Решето Эратосфена" C++
C++ Найти все такие простые числа, не превосходящие заданного N, в троичной записи которых цифра 2, встречается заданное число раз
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dihlofos
Бродяга
 Аватар для dihlofos
302 / 256 / 17
Регистрация: 27.08.2010
Сообщений: 553
20.10.2010, 07:53     Найти все простые числа, не превышающие число n, используя решето Эратосфена #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;
}
st_dent
64 / 64 / 3
Регистрация: 05.07.2010
Сообщений: 219
20.10.2010, 14:43     Найти все простые числа, не превышающие число n, используя решето Эратосфена #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;
}
tontb
0 / 0 / 0
Регистрация: 19.10.2010
Сообщений: 9
20.10.2010, 15:55  [ТС]     Найти все простые числа, не превышающие число n, используя решето Эратосфена #4
спасибо за помощь!)
Ksen111
0 / 0 / 0
Регистрация: 07.12.2015
Сообщений: 9
12.09.2016, 15:49     Найти все простые числа, не превышающие число n, используя решето Эратосфена #5
подскажите, а как сделать, чтобы функция находила все простые числа методом эратосфена?
zer0mail
2188 / 1871 / 187
Регистрация: 03.07.2012
Сообщений: 6,661
Записей в блоге: 1
12.09.2016, 22:02     Найти все простые числа, не превышающие число n, используя решето Эратосфена #6
Цитата Сообщение от Ksen111 Посмотреть сообщение
подскажите, а как сделать, чтобы функция находила все простые числа методом эратосфена?
Что значит "все простые"? Простых чисел бесконечно много
Yandex
Объявления
12.09.2016, 22:02     Найти все простые числа, не превышающие число n, используя решето Эратосфена
Ответ Создать тему
Опции темы

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