0 / 0 / 0
Регистрация: 31.01.2016
Сообщений: 4
1

Поиск простых чисел

23.04.2018, 02:06. Показов 11299. Ответов 4

Всем привет, прохожу книгу Шилдта и остановился на программе:
----------------------------------------------------
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include<conio.h>
using namespace std;
 
int main()
{
  int i, j;
 
  for (i = 2; i < 1000; i++){
    for (j = 2; j <= (i / j); j++){
      if (!(i % j)) break;
 
    if (j > (i / j)) cout << i << " - simple number\n";
  }
  _getch();
return 0;
}
----------------------------------------------------
Пара вопросов:
1) Объясните алгоритм по шагам, если можно.
2) Например, почему берутся делители в диапазоне [ j <= (i / j)]
3) Почему if (j > (i / j)) cout << i << " - simple number\n"; А не if (i == j)
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.04.2018, 02:06
Ответы с готовыми решениями:

Поиск простых чисел
Почему мне возвращает просто непарные числа? в чем загвоздка #include &lt;iostream&gt; bool...

Поиск простых чисел
#include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;locale.h&gt; using namespace std; int y;...

поиск простых чисел
Как найти количество цифр n- значных чисел, у которых сумма любых двух соседних цифр является...

Поиск простых чисел
необходимо найти все простые числа от 1 до 100. Вот я написал код: #include &lt;iostream&gt; #include...

4
308 / 220 / 74
Регистрация: 23.05.2011
Сообщений: 981
23.04.2018, 02:30 2
Лучший ответ Сообщение было отмечено dorito как решение

Решение

Цитата Сообщение от dorito Посмотреть сообщение
Например, почему берутся делители в диапазоне [ j <= (i / j)]
Если число делится на любое число до его корня, другой делитель будет больше корня.
Значение i/j при увеличении j рано или поздно станет приблизительно равным корню.

На мой взгляд, эта запись не очень удачная по двум причинам:
1) она действительно непонятная
2) обе части сравнения постоянно меняются
3) деление — довольно медленная операция.

Сравнение j*j<=i намного лучше, кмк.
Вообще, намного лучше сделать так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
std::cout<<2<< " is simple"<<std::endl; // Сразу выведем единственное чётное простое число
for (int i = 3; i< N; i+=2) // Отсекаем все чётные, то есть половину
{
  bool fl = true; // флаг чётности
  for( int j = 3; j*j<=i; j+=2) // Опять же, не нужно проверять на делимость на чётные
  {
    if(i%j == 0)
    {
      fl = false;
      break; // нет смысла дальше проверять
    }
  if(fl) std::cout<< i<< " is prime"<<std::endl;
}
Ещё, если мы выбираем все простые числа до некоторого, имеет смысл запоминать все простые числа (записывая их в вектор, например) и проверять на делимость только на простые числа меньше корня. Но это более затратно по памяти, конечно же.

Добавлено через 2 минуты
Цитата Сообщение от dorito Посмотреть сообщение
3) Почему if (j > (i / j)) cout << i << " - simple number\n"; А не if (i == j)
Потому что цикл прерывается как только j станет больше, чем корень из i. Из-за этого i никогда не будет равным j, кроме самого первого числа.

Добавлено через 8 минут
Пример того, как можно сделать запоминание, вот:Дан файл с числами Вывести на экран самое маленькое простое число которого нету в этом файле
1
0 / 0 / 0
Регистрация: 31.01.2016
Сообщений: 4
23.04.2018, 12:25  [ТС] 3
Спасибо, но я все-же не понял почему j*j<=i предел
0
308 / 220 / 74
Регистрация: 23.05.2011
Сообщений: 981
23.04.2018, 14:18 4
Если j больше корня из i, то j*j>i, очевидно же.
Выше я пояснял, что нет смысла проверять на делимость на числа больше корня, если на меньшие не делится.
1
0 / 0 / 0
Регистрация: 31.01.2016
Сообщений: 4
24.04.2018, 12:39  [ТС] 5
разобрался в программе, спасибо, такое написание более логично выглядит.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.04.2018, 12:39
Помогаю со студенческими работами здесь

Поиск простых чисел
хочу написать программу по поиску простых чисел вот что у меня есть #include &lt;iostream&gt;...

Поиск простых чисел
Знаю, что тема избитая, но решил написать алгоритм поиска простых чисел. int j,i,k /*количество...

Поиск простых чисел
to idetify if the given K is prime or not. Prime number is the number that can be divided by 1 and...

Поиск простых чисел
Народ, в программе нужно из введённых чисел найти и вывести простые числа(т.е. 2,3,5,7,11,13... и...


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

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

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