Подскажите, как сократить время работы кода? Проверка на простое число

@kruglov1 · Регистрация: 04.10.2014

Студворк — интернет-сервис помощи студентам

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
using namespace std;
 
int main()
{
    int x, k = 0;
    cin >> x;
 
    for (int i = 1; i <= x; i++)
        if (x % i == 0 )
            k++;
    if (k == 2)
        cout << "prime";
    else
        cout << "composite";
    return 0;
}

программа выясняет, является ли число простым или составным

@NoMasters · 15.03.2015, 15:08

Достаточно перебирать делители до sqrt(x), только условие простоты нужно будет подправить.

@nonedark2008 · 15.03.2015, 15:28

1. Решето Эратосфена
2. Решето Аткина
3. Вероятностный тест Рабина-Миллера

Выбирай на здоровье!

Добавлено через 3 минуты

Сообщение от NoMasters

Достаточно перебирать делители до sqrt(x), только условие простоты нужно будет подправить.

А еще можно перебирать с шагом 2, что позволит отбросить ненужную половину четных чисел.

@_Valera_ · 15.03.2015, 17:11

Сообщение от kruglov1

for (int i = 1; i <= x; i++)
if (x % i == 0 )
k++;

1) Очевидно что в любом случае число делится без остатка на себя самого и на 1, то есть уже: time-2;
2) Так же число без остатка может делится только на "половину себя" то есть time / 2; более того:

Сообщение от NoMasters

Достаточно перебирать делители до sqrt(x)

и

Сообщение от nonedark2008

А еще можно перебирать с шагом 2, что позволит отбросить ненужную половину
четных чисел.

Так что все віглядит примерно так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <math.h>
 
using namespace std;
 
void main()
{
    int x, k = 2;
    cin >> x;
    if(x%2 == 0 && x != 2)++k;
 
    for (int i = 3; i <= pow(x,1.0/2); i+=2)
        if (x % i == 0 ) k++;
    if (k == 2)cout << "prime";
    else cout << "composite";
    system("PAUSE");
}

@mat_for_c · 15.03.2015, 21:50

Сообщение от _Valera_

for (int i = 3; i <= pow(x,1.0/2); i+=2)

каждый раз вычислять корень не есть гуд.

@_Valera_ · 15.03.2015, 21:58

Сообщение от mat_for_c

каждый раз вычислять корень не есть гуд.

то есть вычислить его перед циклом? Спасибо учту!

@Viscont · 16.03.2015, 13:09

Сообщение от _Valera_

for (int i = 3; i <= pow(x,1.0/2); i+=2)
* * * * if (x % i == 0 ) k++;

Зачем считать k?

C++
1
2
3
4
5
6
7
8
9
10
11
12
int x;
double xSqrt;
 
cin >> x;
xSqrt = pow(x, 1.0/2);
 
for (int i = 3; i <= xSqrt; i+=2)
        if (x % i == 0 )
        {
            cout << "prime";
           break;
       }

Добавлено через 18 минут
Совсем забыл. Нужно перед циклом проверить делимость на 2

@_Valera_ · 16.03.2015, 13:27

Сообщение от Viscont

Зачем считать k?

+1.

@Viscont · 16.03.2015, 13:32

Сообщение от Viscont

Совсем забыл. Нужно перед циклом проверить делимость на 2

Сам себя запутал. Мы же проверяем на простоту только нечетные числа. А нечетные не делятся на 2

Добавлено через 2 минуты
Хотя цифра 2 является простым "числом"

ValeryS · 16.03.2015, 13:35

тема периодически возникает

вот например одна из них
Быстрая проверка натурального числа на простоту
видать поиск не работает

@gogaloh · 16.03.2015, 17:52

Математики проверят число только до половины.

ValeryS · 16.03.2015, 18:12

Сообщение от gogaloh

Математики проверят число только до половины.

дог корня

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка SDL3 из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

@NoMasters Псевдослучайный 1946 / 1146 / 98 Регистрация: 13.09.2011 Сообщений: 3,215
	15.03.2015, 15:08
	Достаточно перебирать делители до sqrt(x), только условие простоты нужно будет подправить. 0

ValeryS Модератор 8981 / 6748 / 921 Регистрация: 14.02.2011 Сообщений: 23,871
	16.03.2015, 13:35
	тема периодически возникает вот например одна из них Быстрая проверка натурального числа на простоту видать поиск не работает 0

@gogaloh -80 / 27 / 1 Регистрация: 14.03.2015 Сообщений: 811
	16.03.2015, 17:52
	Математики проверят число только до половины. 0