Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
DanilSolar
0 / 0 / 0
Регистрация: 23.04.2015
Сообщений: 6
#1

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

17.05.2016, 11:08. Просмотров 2097. Ответов 13
Метки с++ (Все метки)

Заранее прошу прощения за , возможно, глупые вопросы, так как я новичок и на форуме и в програмировании. Начал с С++ (знаю не лучший выбор для новичка, но назад пути нет), по самоучителю Г. Шилдта (Как оказалось, тоже не лучший выбор). Столкнулся со следующей задачей:Напишите программу, которая находит все простые числа в диапазоне от 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

Может кто-то помочь и объяснить "на пальцах", на примере любого простого числа этот вариант решения, чтобы я въехал. Какие ещё варианты могут быть?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2016, 11:08
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найти все простые числа в диапазоне от 1 до 100 (C++):

Найти все простые числа в диапазоне - C++
Вообщем, такая дилемма, С++ только начали, уже задали задачу: пользователь вводит начало и конец диапазона, нужно вывести все простые...

Найти все простые числа в заданном диапазоне - C++
Найти все простые числа в промежутке между натуральными числами а и b (а &gt; 2000, b - а ≥ 20)

Найти все простые числа в заданном диапазоне и вывести их на экран - C++
Доброго времени суток! Есть задачка, есть кривое решение. :) Суть задачки такова: найти все простые числа до 1000 и вывести их на...

Цикл: Найти и напечатать все простые числа, меньше 100 - C++
Надо написать программу, которая находит и печатает все простые числа меньше 100, дайте, пожалуйста, пример, от которого можно...

Найти все простые числа из интервала от 100 до 1000, используя логическую функцию - C++
Нужно написать программу, буду премного благодарен) Знаю, что на самом деле тут всё просто, но я только начал учиться и пока не совсем...

Вывести все простые числа в диапазоне от a до b - C++
Напишите программу , которая вводит натуральные числа a и b и выводит все простые числа в диапазоне от a до b . Здравствуйт, помогите...

13
zer0mail
2447 / 2081 / 205
Регистрация: 03.07.2012
Сообщений: 7,563
Записей в блоге: 1
17.05.2016, 11:21 #2
Код следует обрамлять в тег [CPP], значок C++. Иначе его даже читать не стоит. Что выдаст программа для 2?

Хочешь освоить язык - напиши свой код. Тогда большинство вопросов типа "зачем тут..." сами исчезнут.
0
DanilSolar
0 / 0 / 0
Регистрация: 23.04.2015
Сообщений: 6
17.05.2016, 11:29  [ТС] #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 минут
Спасибо за совет. Но я сначала хотел бы разобраться в нюансах. В книге все сжато и не всегда с первого раза удается понять что нужно писать. Я написал свой код, он оказался в корне неверным и после этого я заглянул в ответ.
0
Рыжий Лис
Просто Лис
887 / 425 / 125
Регистрация: 17.05.2012
Сообщений: 1,711
Записей в блоге: 4
17.05.2016, 12:04 #4
Писать код - это скучно. Нужно сначала придумать алгоритм.

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

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

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

Быстрее работает так:
C++
1
2
3
4
if ((i%j) == 0) {
   isprime = false;
   break; //зачем что-то делать дальше, если уже известно, что число не простое
}
1
DanilSolar
0 / 0 / 0
Регистрация: 23.04.2015
Сообщений: 6
17.05.2016, 13:10  [ТС] #5
Рыжий Лис, Согласен. Алгоритм мне понятен, а вот как он реализуется мне не понятно. Простое число, то число которое можно без остатка поделить только на 1 и на само себя. Я правильно понимаю, что с каждым ходом первого цикла for, второй цикл for также приращивается на 1? Вот эта строчка
Цитата Сообщение от DanilSolar Посмотреть сообщение
for (j = 2; j <= i/2; j++)
не укладывается в голове. Почему j меньше либо равно результату деления i/2? Спасибо
0
zer0mail
2447 / 2081 / 205
Регистрация: 03.07.2012
Сообщений: 7,563
Записей в блоге: 1
17.05.2016, 13:33 #6
Потому что алгоритм фиговый. Более эфффективный - проверка в цикле нечетных делителей, не превышающих корня из i, те
C++
1
for (j = 3; j*j <= i; j+=2)
1
mimicria
return (true);
1960 / 1097 / 91
Регистрация: 19.04.2011
Сообщений: 2,345
17.05.2016, 14:33 #7
Цитата Сообщение от zer0mail Посмотреть сообщение
Более эфффективный - проверка в цикле нечетных делителей, не превышающих корня из i
Возьмём не простое число 16.
На 3 не делится без остатка, 5 уже не проверяется (квадрат больше), по вашему эффективному алгоритму число простое?
0
dcshowcousa
26 / 18 / 48
Регистрация: 22.10.2015
Сообщений: 303
17.05.2016, 14:34 #8
mimicria, полагаю предварительно идёт проверка на делимость на 2
0
mimicria
return (true);
1960 / 1097 / 91
Регистрация: 19.04.2011
Сообщений: 2,345
17.05.2016, 14:35 #9
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от DanilSolar Посмотреть сообщение
не укладывается в голове. Почему j меньше либо равно результату деления i/2?
Внешний цикл - перебор чисел до 100
Внутренний цикл - перебор делителей.
Возьмите любое число - если до его половины делители не найдены, то дальше и не найдутся.
1
DanilSolar
0 / 0 / 0
Регистрация: 23.04.2015
Сообщений: 6
17.05.2016, 16:38  [ТС] #10
Всем спасибо, после 30 минут чириканья на листе бумаги разобрался как пользоваться циклом For.
0
zer0mail
2447 / 2081 / 205
Регистрация: 03.07.2012
Сообщений: 7,563
Записей в блоге: 1
17.05.2016, 18:37 #11
Цитата Сообщение от mimicria Посмотреть сообщение
Возьмём не простое число 16.
Я писал про проверку в цикле. Проверка на числа 0,1,2 и четность делается до цикла. Неужели трудно сообразить?
0
Дример
0 / 0 / 0
Регистрация: 25.05.2017
Сообщений: 4
26.05.2017, 18:07 #12
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main () {
 
    vector<int> simplies;
    bool issimple = true;
 
    //Находим простые числа
 
    for (int i = 2; i < 100; i++) { // Зачем писать int i = 1, если первое просто число 2
 
        issimple = true;
 
        for (int g = 2; g < 100; g++) { 
            if (i > g && (i % g) == 0) // Если число делится на другое без остатка, то оно уже не простое. В расчёт не берём случай, когда числа делится на само себя и число делится на один(g = 2, i > g)
                issimple = false;
        }
 
        if (issimple) // эквиваленто (issimple == true)
            simplies.push_back(i);
    }
 
    // Выводим простые числа
 
    for (int i = 0; i < simplies.size(); i++)
        cout << simplies[i] << endl;
 
}
0
JustLearn
0 / 0 / 0
Регистрация: 21.10.2017
Сообщений: 28
09.02.2018, 15:36 #13
Можно так:
#include <iostream> // для средства ввода-вывода cout
#include <conio.h> // для функции _getch() которая не даёт программе завершится, ждёт нажатия любой клавиши
using namespace std;
int main() {
int counter; // счётчик
setlocale(LC_ALL, "Ru");
for (int i = 1; i <= 100; i++) {
counter = 0;
for (int j = 1; j <= i; j++) {
if (i%j == 0) {
counter++; /*если число i,
например, на первом этапе первого цикла равное 1
делится без остатка на j = 1,
то счётчику +1. */
}
}
if (counter <= 2) { /* если у числа, два или меньше делитетелей, то оно простое, например
число 2 делится на 1 и на само себя,
того два делителя, значит 2 простое */
cout << i << endl;
}
}
_getch();
}
0
zer0mail
2447 / 2081 / 205
Регистрация: 03.07.2012
Сообщений: 7,563
Записей в блоге: 1
09.02.2018, 16:07 #14
Цитата Сообщение от JustLearn Посмотреть сообщение
Можно так:
Лучше не так.
0
09.02.2018, 16:07
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.02.2018, 16:07
Привет! Вот еще темы с ответами:

Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа - C++
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа. Простые числа это когда они делятся только...

Вывести все простые числа в заданном диапазоне, которые являются палиндромами - C++
Напишите программу , которая выводит все простые числа , которые являются палиндромами ( то есть имеют симметричную запись в десятичной...

Найти простые числа в диапазоне от 1 до 1000 - C++
Задание звучит так Написать программу поиска простых чисел из множества натуральных чисел от 1 до 1000 и записи их в массив. Записать на...

Вывести все простые числа от 0 до 100 (цикл while) - C++
Подскажите пожалуйста как при помощи цикла while и проверки вывести на экран все простые числа от 0 до 100. (1,3,5,7,11,13,17....)


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru