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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 5.00
DeniZz
0 / 0 / 0
Регистрация: 25.10.2010
Сообщений: 10
25.10.2010, 18:56     Найти простые числа пользуясь методом решета Эратосфена НЕ используя массивы #1
Задача формулируется простыми словами: найти простые числа 0..N пользуясь методом решета Эратосфена НЕ используя массивы. Препод сказал задача не тревиальная и решимая.
З.Ы. Учить С мы только начали, следовательно ниче такого сверх-сверх в проге юзать низзя. Хотяя... Но сам лично в си немного шарю. В консольном пока только)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.10.2010, 18:56     Найти простые числа пользуясь методом решета Эратосфена НЕ используя массивы
Посмотрите здесь:

C++ Найти все простые числа, не превышающие число n, используя решето Эратосфена
C++ помогите разобрать самоучке простые числа через массивы
C++ Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
Число простых чисел от 1 до N методом решета Сундарама C++
Найти все простые числа из интервала от 100 до 1000, используя логическую функцию C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
25.10.2010, 21:04     Найти простые числа пользуясь методом решета Эратосфена НЕ используя массивы #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
 
int main()
{
   int i, j;
   int SZ = 100; // предел поиска простых чисел
   for (i = 2; i < SZ; i++) //перебираем числа
   {
      bool y = 1;
      for (j = 2; j < i; j++)
            if (i%j == 0) {y = 0; break;} // значит не простое
      if(y) std::cout << i << std::endl;
   }
 
   return 0;
}
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
25.10.2010, 21:54     Найти простые числа пользуясь методом решета Эратосфена НЕ используя массивы #3
для скорости

1) 2 лучше проверять отдельно
остальные же проверять как 3,5,7,9,...

2) достаточно проверять не до i, а до корня из i
то есть пока j*j<i
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
27.10.2010, 14:41     Найти простые числа пользуясь методом решета Эратосфена НЕ используя массивы #4
odip, так?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
 
int main()
{
   int i, j;
   int SZ = 100;            // предел поиска простых чисел
   for (i = 2; i < SZ; i++) //перебираем числа
   {
      bool y = 1;           // пусть будет простое
      if (i%2 == 0) y = 0;  //делится нацело на 2, значит не простое
      for (j = 3; (j*j <= i) && y; j+=2)
            if (i%j == 0) {y = 0; break;} // делится нацело на какое
                           //нибудь число до корня значит не простое
      if(y) std::cout << i << std::endl;
   }
   return 0;
}
Yandex
Объявления
27.10.2010, 14:41     Найти простые числа пользуясь методом решета Эратосфена НЕ используя массивы
Ответ Создать тему
Опции темы

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