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

Найти все простые числа в диапазоне от 1 до 100 - C++

Восстановить пароль Регистрация
 
DanilSolar
0 / 0 / 0
Регистрация: 23.04.2015
Сообщений: 4
17.05.2016, 11:08     Найти все простые числа в диапазоне от 1 до 100 #1
Заранее прошу прощения за , возможно, глупые вопросы, так как я новичок и на форуме и в програмировании. Начал с С++ (знаю не лучший выбор для новичка, но назад пути нет), по самоучителю Г. Шилдта (Как оказалось, тоже не лучший выбор). Столкнулся со следующей задачей:Напишите программу, которая находит все простые числа в диапазоне от 1 до 100. В конце книги дано решение следующего вида.
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
/*
 
Найдем простые числа в диапазоне от 1 до 100
*/
 
#include <iostream>
using namespace std;
 
int main(){
 setlocale (LC_ALL, "Russian");
 int i, j;
 bool isprime;
 
 for (i=2; i<100; i++) {
  isprime = true;
  for (j = 2; j <= i/2; j++) //посомтрим делится ли это число без остатка
   if ((i%j) == 0) isprime = false; //если да, оно не простое
 
  if (isprime)
   cout << i << " простое. \n";
} 
 
  return 0;
}
Возникло недопонимание.
С первым циклом все более менее понятно: инициализируется переменная, проверяется, походит ли она под условие и приращивается на +1, т.е. все числа от 1 до 100.
Не очень понятен второй цикл внцутри него, а именно:
1. зачем нужна перемеренная j
2. зачем в каждом шаге цикла приращивать её на +1

Может кто-то помочь и объяснить "на пальцах", на примере любого простого числа этот вариант решения, чтобы я въехал. Какие ещё варианты могут быть?
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,656
Записей в блоге: 1
17.05.2016, 11:21     Найти все простые числа в диапазоне от 1 до 100 #2
Код следует обрамлять в тег [CPP], значок C++. Иначе его даже читать не стоит. Что выдаст программа для 2?

Хочешь освоить язык - напиши свой код. Тогда большинство вопросов типа "зачем тут..." сами исчезнут.
DanilSolar
0 / 0 / 0
Регистрация: 23.04.2015
Сообщений: 4
17.05.2016, 11:29  [ТС]     Найти все простые числа в диапазоне от 1 до 100 #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
*/Найдем простые числа в диапазоне от 1 до 100
*/
 
#include <iostream>
using namespace std;
 
int main(){
setlocale (LC_ALL, "Russian");
int i, j;
bool isprime;
 
for (i=2; i<100; i++) {
isprime = true;
for (j = 2; j <= i/2; j++) //посомтрим делится ли это число без остатка
if ((i%j) == 0) isprime = false; //если да, оно не простое
 
if (isprime)
cout << i << " простое. \n";
} 
 
return 0;
Добавлено через 6 минут
Спасибо за совет. Но я сначала хотел бы разобраться в нюансах. В книге все сжато и не всегда с первого раза удается понять что нужно писать. Я написал свой код, он оказался в корне неверным и после этого я заглянул в ответ.
Рыжий Лис
Просто Лис
 Аватар для Рыжий Лис
209 / 164 / 44
Регистрация: 17.05.2012
Сообщений: 611
Записей в блоге: 4
17.05.2016, 12:04     Найти все простые числа в диапазоне от 1 до 100 #4
Писать код - это скучно. Нужно сначала придумать алгоритм.

Для начала стоит ответить на один вопрос: Что такое простое число?

А потом: Как определить что чисто простое?

Цитата Сообщение от DanilSolar Посмотреть сообщение
Не очень понятен второй цикл внцутри него,
Это делители. Некое число, например, 80 делим на 2, 3, 4, 5, 6 ... 40. Если разделилось без остатка, то число не простое.

Быстрее работает так:
C++
1
2
3
4
if ((i%j) == 0) {
   isprime = false;
   break; //зачем что-то делать дальше, если уже известно, что число не простое
}
DanilSolar
0 / 0 / 0
Регистрация: 23.04.2015
Сообщений: 4
17.05.2016, 13:10  [ТС]     Найти все простые числа в диапазоне от 1 до 100 #5
Рыжий Лис, Согласен. Алгоритм мне понятен, а вот как он реализуется мне не понятно. Простое число, то число которое можно без остатка поделить только на 1 и на само себя. Я правильно понимаю, что с каждым ходом первого цикла for, второй цикл for также приращивается на 1? Вот эта строчка
Цитата Сообщение от DanilSolar Посмотреть сообщение
for (j = 2; j <= i/2; j++)
не укладывается в голове. Почему j меньше либо равно результату деления i/2? Спасибо
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,656
Записей в блоге: 1
17.05.2016, 13:33     Найти все простые числа в диапазоне от 1 до 100 #6
Потому что алгоритм фиговый. Более эфффективный - проверка в цикле нечетных делителей, не превышающих корня из i, те
C++
1
for (j = 3; j*j <= i; j+=2)
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
17.05.2016, 14:33     Найти все простые числа в диапазоне от 1 до 100 #7
Цитата Сообщение от zer0mail Посмотреть сообщение
Более эфффективный - проверка в цикле нечетных делителей, не превышающих корня из i
Возьмём не простое число 16.
На 3 не делится без остатка, 5 уже не проверяется (квадрат больше), по вашему эффективному алгоритму число простое?
dcshowcousa
25 / 17 / 48
Регистрация: 22.10.2015
Сообщений: 303
17.05.2016, 14:34     Найти все простые числа в диапазоне от 1 до 100 #8
mimicria, полагаю предварительно идёт проверка на делимость на 2
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
17.05.2016, 14:35     Найти все простые числа в диапазоне от 1 до 100 #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от DanilSolar Посмотреть сообщение
не укладывается в голове. Почему j меньше либо равно результату деления i/2?
Внешний цикл - перебор чисел до 100
Внутренний цикл - перебор делителей.
Возьмите любое число - если до его половины делители не найдены, то дальше и не найдутся.
DanilSolar
0 / 0 / 0
Регистрация: 23.04.2015
Сообщений: 4
17.05.2016, 16:38  [ТС]     Найти все простые числа в диапазоне от 1 до 100 #10
Всем спасибо, после 30 минут чириканья на листе бумаги разобрался как пользоваться циклом For.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.05.2016, 18:37     Найти все простые числа в диапазоне от 1 до 100
Еще ссылки по теме:

C++ Найти простые числа в заданном диапазоне (циклы)
Вывести все простые числа в заданном диапазоне, которые являются палиндромами C++
Найти все простые числа в заданном диапазоне C++

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

Или воспользуйтесь поиском по форуму:
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,656
Записей в блоге: 1
17.05.2016, 18:37     Найти все простые числа в диапазоне от 1 до 100 #11
Цитата Сообщение от mimicria Посмотреть сообщение
Возьмём не простое число 16.
Я писал про проверку в цикле. Проверка на числа 0,1,2 и четность делается до цикла. Неужели трудно сообразить?
Yandex
Объявления
17.05.2016, 18:37     Найти все простые числа в диапазоне от 1 до 100
Ответ Создать тему

Метки
с++
Опции темы

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