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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.87
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
#1

Эффективный алгоритм поиска простых чисел на С++ - C++

02.05.2013, 11:41. Просмотров 6083. Ответов 94
Метки нет (Все метки)

Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает. Можете подсказать почему??? Заранее спасибо.
Простое число - которое делится на 1 и на само себя, сложное число-которое делится на 1 и на само себя и на какое-то еще число, 5 -простое число, 10-сложное число.
P.S. Вот программа:
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
32
33
34
35
36
37
38
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
 int simple (int x,int i=1)
{
    int fn;
    for(i=1;i<=x;i++)
    {
        if(i!=1||i!=x)
        {
            if(!(x%i))
            {
                fn=0;
                return fn;
            }
        }
    }
    fn=1;
    return fn;
}
int main()
{
    //ifstream cin("input.txt");
    long int x,i=1;
    cin>>x;
    if(simple(x,i)==0)
    {
        cout<<"composite";
        return 0;
    }
    if(simple(x,i)==1)
    {
        cout<<"prime";
            return 0;
    }
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2013, 11:41
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Эффективный алгоритм поиска простых чисел на С++ (C++):

функция поиска простых чисел - C++
не могу сделать функции для поиска простых чисел, вот код функции int prost(int x) { if (x/2) return true; else ...

Программа поиска простых чисел - C++
Необходимо написать программу для поиска простых чесил в интервале от 1 до 100 на языке СИ.Простое число — это натуральное число, имеющее...

Функция для поиска ближайших простых чисел - C++
Ув. товарищи программисты , нужна помощь. Требуется функция с помощью которой можно найти 2 ближайших ПРОСТЫХ числа к веденному числу. ...

Почему программа поиска простых чисел работает только до 61? - C++
Добрый день, Помогите, пожалуйста, разобраться. Программа для поиска простых чисел. На экран отображает только простые числа до 61, ...

Алгоритм нахождения простых чисел - C++
Не могу найти в интернете нормальный код алгоритма нахождения простых чисел. Помогите пожалуйста. Добавлено через 2 минуты ...

Алгоритм нахождения простых чисел - C++
Вопросы: 1) Нужен алгоритм проверки числа (является ли число простим). Нужно чтобы алгоритм был быстрым (нужно проделать 104 операций за...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 12:29 #2
NaikoN,
Цитата Сообщение от NaikoN Посмотреть сообщение
простое число или сложное
может простое или составное ?

Добавлено через 1 минуту
NaikoN,
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
long long mulmod(long long a, long long b, long long MOD){
    if (b == 0) return 0;
    long long res = mulmod(a, b >> 1, MOD);
    res += res;
    res %= MOD;
    return (b & 1)? (a + res) % MOD : res;
}
 
bool witness(long long a, long long n){
    long long d = 1;
    long long b = n - 1;
    for(int i = 63; i >= 0; i--){
        if(b < pow(2.0, i)) continue;
        long long x = d;
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1) return true;
        if ((b >> i) & 1) d = mulmod(d, a, n);
    }
    return (d != 1);
}
 
bool MillerRabin(long long n, long long tries){
    for(int it = 0; it < tries; it++){
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
MillerRabin (ваше число, 19) = true, если простое, false, если составное

Добавлено через 3 минуты
NaikoN, а вот примитивный вариант :
C++
1
2
3
4
5
6
cin >> a;
for(j = 2; j * j <= a && a % j; ++j);
if(j * j > a && a - 1) 
    puts("YES"); 
else 
    puts("NO");
0
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 13:40  [ТС] #3
Ternsip, Как написать примитивный вариант я знаю Мне не понятно почему в моей программе не работает цикл, подскажите??
P.S. Да, простое и составное число, перепутал.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 14:01 #4
NaikoN, Потому что вы её вообще неправильно написали
C++
1
2
3
4
int simple (int a){
 for(j = 2; j * j <= a && a % j; ++j);
 return (j * j > a && a - 1);
}
0
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 14:55  [ТС] #5
Ternsip, Разве в строке
C++
1
 int simple (int a){
не нужно еще объявить
C++
1
int j
???
P.S. В вашем примере цикл точно так же не работает как и у меня. Например я ввожу значение а=10, а переменная j дотигает значения аж 66. Как такое может быть?? Ведь цикл должен идти по а????и j не может быть больше 10.
Я понимаю, что задаю наверное глупые и некорректные вопросы, но просто хочу разобраться.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 14:59 #6
NaikoN, детский сад
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <cmath>
 
using namespace std;
 
int simple (int a){
    int j;
    for(j = 2; j * j <= a && a % j; ++j);
    return (j * j > a && a - 1);
}
 
int main(){
    int n;
    cin >> n;
    cout << simple(n);
    return 0;
}
Добавлено через 37 секунд
NaikoN, выводит 1 если число простое, 0 иначе
0
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 15:13  [ТС] #7
Ternsip, А можно пожалуйста расписать вот эти две строчки
C++
1
2
for(j = 2; j * j <= a && a % j; ++j);
    return (j * j > a && a - 1);
А то я не совсем понимаю, что в них происходит и как переменная n которую Вы вводите связана с переменной a по которую идет цикл? Заранее спасибо.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 15:25 #8
Цитата Сообщение от NaikoN Посмотреть сообщение
и как переменная n которую Вы вводите связана с переменной a
в функцию я передаю переменную n, которая скопируется в "а"
это обычный цикл, не знаю как вам ещё объяснить...
0
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 15:32 #9
Цитата Сообщение от NaikoN Посмотреть сообщение
Хотел написать функцию которая вычисляет простое число или сложное,
- всё очень просто
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>
using namespace std;
 
bool isSimple(int num);
 
int main()
{
    int num;
    while( true )
    {
        cout<<"Enter num : ";cin>>num;
        if(isSimple(num))
            cout<<"Number is simple"<<endl;
        else
            cout<<"Number is not simple"<<endl;
    }
    return 0;
}
 
bool isSimple(int num)
{
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    for(int i = 2; i <= 9 && bSimple; i++)
    {
        if( i != num )
            bSimple = num % i != 0;
    }
    return bSimple;
}
0
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 16:04  [ТС] #10
Ternsip, Число 27 составное, т.к. делится на 1,3,9,27.
Вы писали, что "в функцию я передаю переменную n, которая скопируется в "а"
это обычный цикл, не знаю как вам ещё объяснить... ", на основании чего число "n" скопируется в переменную а??
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 16:09 #11
NaikoN, да, про 27 ошибся

Добавлено через 1 минуту
NaikoN,
Цитата Сообщение от NaikoN Посмотреть сообщение
на основании чего число "n" скопируется в переменную а??
да на основании того, что вы передаёте переменную в аргументы функции, если вы передаёте не по ссылке, что вы и делаете, то вы просто скажете, что new int a = n;
1
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 16:35  [ТС] #12
Ternsip, Спасибо, на основании вашего кусочка кода вроде написал функцию, вот, что получилось:
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
32
33
34
35
36
#include<iostream>
#include<math.h>
using namespace std;
 int simple (int a)
{
    int fn,i;
    for(i=2;i<=sqrt(a);i++)
    {
        if(i!=1||i!=a)
        {
            if(!(a%i))
            {
                fn=0;//false composite
                return fn;
            }
        }
    }
    fn=1;//true prime
    return fn;
}
int main()
{
    long int x;
    cin>>x;
    if(simple(x)==1)
    {
        cout<<"prime";
        return 0;
    }
    if(simple(x)==0)
    {
        cout<<"composite";
        return 0;
    }
    return 0;
}
Проверяет все числа от 0 до long int.
P.S. Еще раз спасибо!!!
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 16:40 #13
NaikoN,
C++
1
2
3
4
5
6
7
8
9
10
int simple (int a){
    if (a <= 1)
        return false;
    for(int i = 2; i*i <= a; i++) {
        if (a % i == 0) {
            return false;
        }
    }
    return true;
}
молодец, а я немного улучшил вашу функцию, она, практически, ничем не отличается.
0
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 16:44 #14
NaikoN, давай даже проверим мой алгоритм. Так вот я делаю генератор чисел от 0 до 3500 скажем. Сейчас посмотрим вывод моего алгоритма и
500 первых чисел последовательности http://ru.wikipedia.org/wiki/Список_простых_чисел
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
#include <cmath>
#include <iostream>
using namespace std;
 
bool isSimple(int num);
 
int main()
{
    for(int num = 0; num < 3571; num++)
    {
        if(isSimple(num))
            cout<<num<<" ";
    }
    return 0;
}
 
bool isSimple(int num)
{
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    for(int i = 2; i <= 11 && bSimple; i++)
    {
        if( i != num )
            bSimple = num % i != 0;
    }
    return bSimple;
}
0
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 16:48 #15
PS:Я не юзаю стандартные алгоритмы а пишу свои, причём краеугольным камнем в основе моих кодов лежит простота и доступность. Если я в чём то недоглядел, написал что неверно считает я и сам поправлю, т.к никогда никому лажу я не толкаю.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.05.2013, 16:48
Привет! Вот еще темы с ответами:

Алгоритм отбора простых чисел - C++
Сижу учу С++ по Шилтду (Базовый курс) И вот папался такой алгоритм, на котором меня просто заклинило на 2 часа, так и не смог...

Алгоритм нахождения простых чисел - C++
Не так давно начал изучать с++. Вот попытался написать программу которая вычисляет простое ли число которые вы ввели в консоль? но она...

Алгоритм нахождения ПРОСТЫХ чисел в файле - C++
Заполнить файл f целыми числами, полученными с помощью генератора случайных чисел. Из файла f получить файл g, оставив только ПРОСТЫЕ...

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.05.2013, 16:48
Ответ Создать тему
Опции темы

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