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

Простые числа - C++

Восстановить пароль Регистрация
 
scofielcl
4 / 4 / 0
Регистрация: 11.09.2011
Сообщений: 143
13.03.2012, 17:48     Простые числа #1
Доброго дня.
Данный код проверяет ,является ли число простым.
Есть ли альтернативный алгоритм проверки ,более "компактный" ?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <math.h>
using namespace std;
 
int main() {
    int n;
    cin>> n;
    for(int i=2;i<n-1;i++){
        if((n%i)==0){cout<<"Не Простое"<<endl;break;}
        
    }
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.03.2012, 17:48     Простые числа
Посмотрите здесь:

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p. C++
C++ Даны целые числа р и q. Получить все делители числа q, взаимно простые с р
Даны целые числа р и q. Получить все делители числа q, взаимно простые с р. C++
C++ Даны натуральные числа a,b(a<= Ь). Получить все простые числа р, удовлетворяющие неравенствам a<= р<= b.
C++ Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
C++ Одномерный массив. Вывести на экран все числа, индексы которых есть простые числа.
C++ Дано натуральное число. Вывести на экран все простые числа до заданного числа.
Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.03.2012, 17:53     Простые числа #2
Особо компактнее сделать не получиться, можно лишь сделать более эффективным. Самый простой вариант - перебирать только нечетные числа до корня из n. Есть еще, например, тест BPSW, работающий за log(n).
Черный ворон
129 / 123 / 6
Регистрация: 31.01.2012
Сообщений: 435
13.03.2012, 17:54     Простые числа #3
есть очень много алгоритмов нахождения простых чисел. есть способы сократить перебор.
попробуйте почитать про

решето Сундарама, решето Эратосфена.
для вашего же алгоритма могу посоветовать вот такое условие выхода из цикла:
C++
1
for(int i=2;i<sqrt(n);i++)
Yandex
Объявления
13.03.2012, 17:54     Простые числа
Ответ Создать тему
Опции темы

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