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

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

17.05.2016, 11:08. Показов 35148. Ответов 14
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Заранее прошу прощения за , возможно, глупые вопросы, так как я новичок и на форуме и в програмировании. Начал с С++ (знаю не лучший выбор для новичка, но назад пути нет), по самоучителю Г. Шилдта (Как оказалось, тоже не лучший выбор). Столкнулся со следующей задачей:Напишите программу, которая находит все простые числа в диапазоне от 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)
17.05.2016, 11:08
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
17.05.2016, 11:08
Ответы с готовыми решениями:

Перебором делителей найти простые числа в указанном диапазоне, и вывести все простые числа в поле Memo
Мне нужна программка на Delphi, которая простым перебором делителей находит простые числа в указанном диапазоне и выводит все простые числа...

Найти все простые числа в диапазоне от 1 до M.
Найти все простые числа в диапазоне от 1 до M. Преподаватель намекнул на метод &quot;Решето Эратосфена&quot;.

Найти все простые числа в диапазоне от 2 до N
Напишите две программы, которые находят все простые числа в диапазоне от 2 до N двумя разными способами: а) проверкой каждого числа из...

14
2687 / 2259 / 244
Регистрация: 03.07.2012
Сообщений: 8,227
Записей в блоге: 1
17.05.2016, 11:21 2
Код следует обрамлять в тег [CPP], значок C++. Иначе его даже читать не стоит. Что выдаст программа для 2?

Хочешь освоить язык - напиши свой код. Тогда большинство вопросов типа "зачем тут..." сами исчезнут.
0
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
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5966 / 3729 / 1097
Регистрация: 17.05.2012
Сообщений: 10,787
Записей в блоге: 9
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
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
2687 / 2259 / 244
Регистрация: 03.07.2012
Сообщений: 8,227
Записей в блоге: 1
17.05.2016, 13:33 6
Потому что алгоритм фиговый. Более эфффективный - проверка в цикле нечетных делителей, не превышающих корня из i, те
C++
1
for (j = 3; j*j <= i; j+=2)
1
return (true);
 Аватар для mimicria
1976 / 1111 / 221
Регистрация: 19.04.2011
Сообщений: 2,345
17.05.2016, 14:33 7
Цитата Сообщение от zer0mail Посмотреть сообщение
Более эфффективный - проверка в цикле нечетных делителей, не превышающих корня из i
Возьмём не простое число 16.
На 3 не делится без остатка, 5 уже не проверяется (квадрат больше), по вашему эффективному алгоритму число простое?
0
28 / 20 / 97
Регистрация: 22.10.2015
Сообщений: 304
17.05.2016, 14:34 8
mimicria, полагаю предварительно идёт проверка на делимость на 2
0
return (true);
 Аватар для mimicria
1976 / 1111 / 221
Регистрация: 19.04.2011
Сообщений: 2,345
17.05.2016, 14:35 9
Лучший ответ Сообщение было отмечено DanilSolar как решение

Решение

Цитата Сообщение от DanilSolar Посмотреть сообщение
не укладывается в голове. Почему j меньше либо равно результату деления i/2?
Внешний цикл - перебор чисел до 100
Внутренний цикл - перебор делителей.
Возьмите любое число - если до его половины делители не найдены, то дальше и не найдутся.
1
0 / 0 / 0
Регистрация: 23.04.2015
Сообщений: 6
17.05.2016, 16:38  [ТС] 10
Всем спасибо, после 30 минут чириканья на листе бумаги разобрался как пользоваться циклом For.
0
2687 / 2259 / 244
Регистрация: 03.07.2012
Сообщений: 8,227
Записей в блоге: 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
C++
 Аватар для JustLearn
3 / 3 / 1
Регистрация: 21.10.2017
Сообщений: 121
09.02.2018, 15:36 13
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
Можно так:
#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
2687 / 2259 / 244
Регистрация: 03.07.2012
Сообщений: 8,227
Записей в блоге: 1
09.02.2018, 16:07 14
Цитата Сообщение от JustLearn Посмотреть сообщение
Можно так:
Лучше не так.
0
0 / 0 / 0
Регистрация: 15.01.2018
Сообщений: 4
24.12.2019, 21:55 15
Не ругайте сильно, я учусь, на начальном этапе познания я придумал так
C++ (Qt)
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
//13. Заполнить массив первыми n простыми числами
#include <iostream>
using namespace std;
 
void fillArr(int* arr, int N)
{
    int startIndex;
    startIndex = 1;
    int count;
    for (size_t i = 0; i < N; i++) /*Первый for перебирает ячейки массива для записи */
    {
        for (size_t j = startIndex+1;/* j < 100*/; j++) /*Второй for перебирается числа для проверки, начиная с последнего записанного */
        {
            count = 0;
            for (size_t k = 2; k < j; k++)/* Третий for перебирает делители, до проверяемого числа */
            {
                if (j%k==0)
                {
                    ++count;
                }
            }
                if (count == 0)/* Если делителей нет, а в третьем for мы пропускаем 1 и само число, то делаем запись в ячейку [i] массива arr */
            {
                arr[i] = j;
                startIndex = arr[i];
                break;
            }
        }
    }
};
void showArr(int* arr, int N)
{
    for (int i = 0; i < N; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
 
int main()
{
    setlocale(0, "");
    srand(time(NULL));
    int N;
    cout << "Введите размер массива простых чисел: "; cin >> N;
    int *arr = new int[N];
    fillArr(arr, N);
    showArr(arr,N);
    cout << endl;
    return 0;
}
0
24.12.2019, 21:55
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
24.12.2019, 21:55
Помогаю со студенческими работами здесь

Найти все простые числа в диапазоне от N до M
Здравствуйте, прошу помочь с заданием, звучит так: Найти все простые числа в диапазоне от N до M Числа N и M вводятся с клавиатуры....

В диапазоне от А до В найти все простые числа
Нужно упростить программу, вроде есть лишнее действие. Ввести два числа А и В. В диапазоне от А до В найти все простые числа. ...

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

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

Задача: найти все простые числа в диапазоне
Вводятся два числа. Нужно найти все простые числа от A до B. Ограничение по времени - 1 секунда, по памяти - 64Mb. У меня получился вот...


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

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

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Опции темы

Новые блоги и статьи
Обработка массивов с помощью циклов в JavaScript
hw_wired 12.02.2025
Массивы в JavaScript - это упорядоченные наборы элементов, где каждый элемент имеет свой индекс, начиная с нуля. Они невероятно гибки в использовании, позволяя хранить данные любых типов - числа,. . .
Создание каталога и всех родительских каталогов с помощью Python
hw_wired 12.02.2025
Работа с файловой системой - одна из ключевых задач при разработке программного обеспечения. Особенно часто возникает потребность создавать каталоги для хранения файлов, логов, временных данных и. . .
Возврат файла к состоянию указанного коммита Git
hw_wired 12.02.2025
Git - распределенная система контроля версий, без которой сложно представить современную разработку программного обеспечения. Когда речь заходит о восстановлении файлов, Git предоставляет целый. . .
Сброс локальной ветки Git до состояния HEAD удаленного репозитория
hw_wired 12.02.2025
Работая в команде разработчиков, часто сталкиваешься с ситуацией, когда локальная версия кода существенно отличается от той, что находится в центральном репозитории. Такое расхождение может. . .
Запрет подсветки выделения текста с помощью CSS
hw_wired 12.02.2025
Выделение текста - одна из базовых возможностей взаимодействия пользователя с контентом на веб-странице. Однако в некоторых случаях стандартное поведение выделения может нарушать задуманный дизайн. . .
Выполнение другой программы из приложения Python
hw_wired 12.02.2025
При разработке современных приложений часто возникает потребность в запуске и взаимодействии с другими программами прямо из кода. Python предоставляет множество эффективных средств для выполнения. . .
Отличия между let и var в JavaScript
hw_wired 12.02.2025
Работа с переменными - один из основных моментов при написании программ на JavaScript. От правильного объявления и использования переменных зависит не только читаемость кода, но и его надежность, а. . .
Подключение файла JavaScript в других файлах JavaScript
hw_wired 12.02.2025
Самый современный и рекомендуемый способ подключения JavaScript-файлов - использование системы модулей ES6 с ключевыми словами 'import' и 'export'. Этот подход позволяет явно указывать зависимости. . .
Отмена изменений, не внесенных в индекс Git
hw_wired 12.02.2025
Управление изменениями в Git - одна из важнейших задач при разработке программного обеспечения. В процессе работы часто возникают ситуации, когда нужно отменить внесенные изменения, которые еще не. . .
Что такое px, dip, dp, and sp в Android
hw_wired 12.02.2025
При разработке мобильных приложений для Android одним из ключевых вызовов становится адаптация интерфейса под различные устройства. А ведь их действительно немало - от компактных смартфонов до. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru