1 / 1 / 1
Регистрация: 04.10.2014
Сообщений: 38
1

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

15.03.2015, 14:55. Показов 1017. Ответов 11
Метки нет (Все метки)

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;
}
программа выясняет, является ли число простым или составным
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.03.2015, 14:55
Ответы с готовыми решениями:

Как сократить время работы программы?!
Нужно сократить время работы программы по вычислению чисел Фибоначчи: Вот мой код: #include...

Как сократить время работы программы?
Вот текст олимпиадной задачи: Ваша задача – посчитать сумму двух чисел. Входные данные В...

Как сократить время работы программы?
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;...

Как сократить время работы процедуры
Здравствуйте. Собственно, сабж. MSQL. Есть исходная таблица с полями hash, id, value, date. Хочу...

11
Псевдослучайный
1946 / 1145 / 98
Регистрация: 13.09.2011
Сообщений: 3,215
15.03.2015, 15:08 2
Достаточно перебирать делители до sqrt(x), только условие простоты нужно будет подправить.
0
1386 / 1016 / 323
Регистрация: 28.07.2012
Сообщений: 2,804
15.03.2015, 15:28 3
1. Решето Эратосфена
2. Решето Аткина
3. Вероятностный тест Рабина-Миллера

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

Добавлено через 3 минуты
Цитата Сообщение от NoMasters Посмотреть сообщение
Достаточно перебирать делители до sqrt(x), только условие простоты нужно будет подправить.
А еще можно перебирать с шагом 2, что позволит отбросить ненужную половину четных чисел.
0
495 / 377 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
15.03.2015, 17:11 4
Цитата Сообщение от 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");
}
0
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972
15.03.2015, 21:50 5
Цитата Сообщение от _Valera_ Посмотреть сообщение
for (int i = 3; i <= pow(x,1.0/2); i+=2)
каждый раз вычислять корень не есть гуд.
0
495 / 377 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
15.03.2015, 21:58 6
Цитата Сообщение от mat_for_c Посмотреть сообщение
каждый раз вычислять корень не есть гуд.
то есть вычислить его перед циклом? Спасибо учту!
0
0 / 0 / 0
Регистрация: 16.03.2015
Сообщений: 2
16.03.2015, 13:09 7
Цитата Сообщение от _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
0
495 / 377 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
16.03.2015, 13:27 8
Цитата Сообщение от Viscont Посмотреть сообщение
Зачем считать k?
+1.
0
0 / 0 / 0
Регистрация: 16.03.2015
Сообщений: 2
16.03.2015, 13:32 9
Цитата Сообщение от Viscont Посмотреть сообщение
Совсем забыл. Нужно перед циклом проверить делимость на 2
Сам себя запутал. Мы же проверяем на простоту только нечетные числа. А нечетные не делятся на 2

Добавлено через 2 минуты
Хотя цифра 2 является простым "числом"
0
Модератор
Эксперт по электронике
8734 / 6525 / 886
Регистрация: 14.02.2011
Сообщений: 22,839
16.03.2015, 13:35 10
тема периодически возникает
вот например одна из них
Быстрая проверка натурального числа на простоту
видать поиск не работает
0
20 / 27 / 1
Регистрация: 14.03.2015
Сообщений: 792
16.03.2015, 17:52 11
Математики проверят число только до половины.
0
Модератор
Эксперт по электронике
8734 / 6525 / 886
Регистрация: 14.02.2011
Сообщений: 22,839
16.03.2015, 18:12 12
Цитата Сообщение от gogaloh Посмотреть сообщение
Математики проверят число только до половины.
дог корня
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.03.2015, 18:12
Помогаю со студенческими работами здесь

Сократить время работы и выделяемую память
Помогите оптимизировать программу. using System; class Program { static void...

Нужно сократить время работы программы
number_of_words = int(input()) if number_of_words &gt; 100000: exit(0) words = anagrammbl =...

Модификация кода: сократить время бинарного поиска
Можете подсказать, как сократить время бинарного поиска тута: #include&lt;stdio.h&gt; main() {int...

Счастливый билет. Надо сократить время работы программы
Написал 2 программы обе работают очень долго первая 19сек вторая 15сек А надо: Лимит времени...


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

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

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