Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.53/43: Рейтинг темы: голосов - 43, средняя оценка - 4.53
0 / 0 / 0
Регистрация: 19.10.2010
Сообщений: 9
1

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

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

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

помогите написать программу пожалуйста!
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.10.2010, 23:37
Ответы с готовыми решениями:

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

Разложить число на простые множители, используя решето Эратосфена
Могли бы вы мне объяснить, как разложить число на простые множители, используя решето Эратосфена?

Вывести простые числа используя решето Эратосфена
Напишите программу, которая выводит все простые числа в диапазоне от 2 до N ( N заранее...

Как разложить число на простые множители, используя решето Эратосфена?
Я только код для решета Эратосфена знаю(

5
Бродяга
313 / 267 / 56
Регистрация: 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
64 / 64 / 12
Регистрация: 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
0 / 0 / 0
Регистрация: 19.10.2010
Сообщений: 9
20.10.2010, 15:55  [ТС] 4
спасибо за помощь!)
0
0 / 0 / 0
Регистрация: 07.12.2015
Сообщений: 9
12.09.2016, 15:49 5
подскажите, а как сделать, чтобы функция находила все простые числа методом эратосфена?
0
2626 / 2211 / 237
Регистрация: 03.07.2012
Сообщений: 7,990
Записей в блоге: 1
12.09.2016, 22:02 6
Цитата Сообщение от Ksen111 Посмотреть сообщение
подскажите, а как сделать, чтобы функция находила все простые числа методом эратосфена?
Что значит "все простые"? Простых чисел бесконечно много
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.09.2016, 22:02

Вывести все простые числа алгоритмом Решето Эратосфена
Моя задача вывести в файл все простые числа из диапазона . Для отбора простых чисел использовать...

Дано натуральное число n. Найти все меньшие n простые числа, используя решето Эратосфена
4. Дано натуральное число n (n≥2). Найти все меньшие n простые числа, используя решето Эратосфена....

Найти все простые числа, меньше n, используя решето Эратосфена
Заданное натуральное число n (n больше-равно 2). Найти все простые числа, меньше n, используя...

Найти все меньшие n простые числа, используя решето Эратосфена
Дано натуральное число n (n≥2). Найти все меньшие n простые числа, используя решето Эратосфена....


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru