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

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

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

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

02.05.2013, 11:41. Просмотров 6276. Ответов 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 операций за...

94
-=ЮрА=-
02.05.2013, 18:55     Эффективный алгоритм поиска простых чисел на С++
  #31

Не по теме:

-=ЮрА=-, если придумаете алгоритм много быстрее, то может удостоитесь награды и похвалы выше чем сам
- быстрее на многоядерной машине я могу распараллелить так что ты и глазом не моргнёшь а ПК выведет большую часть известного числового ряда. Если придумаете...я уже вон выше привёл в 3 раза эффективней причём код написал сидя смотря мульт и играя с дочерью, а не обложившись справочниками и прочей атрибутикой, пффф...

0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 18:57 #32
-=ЮрА=-, вы написали очень не эффективный код, вы тестировали алгоритмы на маленьких числах, попробуйте на числах больше миллиарда.
0
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 19:03 #33
Ternsip, хорош!Возьми да посмотри на цифры. И в нуле поправь свой "супер"код.

Добавлено через 55 секунд

Не по теме:

Хотя миллиард говоришь, ну хорошо...



Добавлено через 4 минуты
Ternsip, especially for you (ну не миллиард а 100 млн, простишь меня ладно?)
Юзни код мєйна
У меня
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    int nCount  = 0;
/*  for(int num = 0; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
//      else
//          continue;
//      if( nCount && nCount % 80 == 0 )
//          system("pause");
    }*/
    isSimple(100000000);
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0;
}
и у себя
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
    int nCount  = 0;
   /* for(int num = 1; num <= 3571; num++)
    {
        if(test(num))
            cout<<(nCount++)<<" - "<<num<<endl;
     //   else
       //     continue;
      //  if( nCount && nCount % 80 == 0 )
        //    system("pause");
    }*/
    test(100000000);
 
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0; 
}
И погляди результат 82 операции у тебя и 2 у меня.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 19:06 #34
http://www.cyberforum.ru/attachment....1&d=1367507123
http://www.cyberforum.ru/attachment....1&d=1367507123
http://www.cyberforum.ru/attachment....1&d=1367507123
0
Миниатюры
Эффективный алгоритм поиска простых чисел на С++   Эффективный алгоритм поиска простых чисел на С++   Эффективный алгоритм поиска простых чисел на С++  

Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 19:06 #35
-=ЮрА=-, 100000000 разделится сразу на двойку, я вам говорю попробуйте тест 9999999900000001
0
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 19:09 #36
Ternsip, у меня стоит тип инт у которого есть предел INT_MAX, а ты тулишь числа превосходящие его. (Даю подсказку замени int num на long long num, а то не догадаешся до этого видимо)
Я поставил isSimple(899999999); и получил 14 операций у себя и test(899999999); - 84 на твоём коде, это всё экстраполируется и на большие числа
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 19:10 #37
-=ЮрА=-, какую же вы ерунду пишете посмотрите 1-й скриншот.
0
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 19:15 #38
Всё вот тебе код и умолкни наконец
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
#include <cmath>
#include <iostream>
using namespace std;
 
bool isSimple(long long num);
double OPCount = 0;
 
int main()
{
    isSimple(9999999900000001);
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long long num)
{
    int i;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    OPCount += 1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    num /= 10;
    for(i = 9 + 2; i <= num / 10 && bSimple; i += 2)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    return bSimple;
}
0
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 19:17 #39
-=ЮрА=-, только 9999999900000001 простое число, а у вас программа скажет, что оно составное isSimple вернёт false
1
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 22:46 #40
Цитата Сообщение от Ternsip Посмотреть сообщение
-=ЮрА=-, только 9999999900000001 простое число, а у вас программа скажет, что оно составное isSimple вернёт false
- да ты что(научись компилить лучше), я тебе уже писал что присваивать long long к инту может только человек заведомо пытающийся предоставить подвох
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
39
40
41
42
43
44
45
46
47
48
49
50
#include <cmath>
#include <iostream>
using namespace std;
 
bool isSimple(long long num);
double OPCount = 0;
 
int main()
{
    long long nCount  = 0;
    long long num     = 0;
    for(num; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
        else
            continue;
        if( nCount && nCount % 80 == 0 )
            system("pause");
    }
    cout<<"Total count of operations : "<<OPCount<<endl;
    if(isSimple(9999999900000001))
        cout<<"IS SIMPLE"<<endl;
    if(isSimple(2147483647))
        cout<<"IS SIMPLE"<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long long num)
{
    long long i  = 0;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    OPCount += 1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    for(i = 9 + 2; i <= 100 && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        OPCount += 1;
    } 
    return bSimple;
}
https://ideone.com/XaVpci
497 - 3547
498 - 3557
499 - 3559
500 - 3571
Total count of operations : 39337
IS SIMPLE
IS SIMPLE
Добавлено через 2 минуты

Не по теме:

В любом случае алгоритм представленный мной обладает производительностью на порядок выше того что ты пытаешся представить как панацею, вдобавок у тебя не работает нолик. Про длинну и понятность кода я молчу...

0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 23:06 #41
-=ЮрА=-,Ваша последняя программа по-прежнему не работает, число 1244042141 не простое, а она говорит, что простое. 1244042141 делится на 181
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 06:46 #42
Мой алгоритм работает,до ИНТ_МАХ. Хорошо через пару часов еще немного доработав получу универсальный код,ты лучше свой код доработай по тем замечаниям которые даны выше.Поверь я доведу до момента когда ответишь за свои слова, держись малыш)))
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.05.2013, 08:42 #43
Позволю себе поучаствовать в этом безобразии, т.к. делать нечего.
-=ЮрА=- ваша последняя программа ( та, которая с этим циклом
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
C++
1
for(i = 9 + 2; i <= 100 && bSimple; i += 2)
) способна искать простые числа не больше 10000 (1002).

Делая так,
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
C++
1
isSimple(9999999900000001)
вы хитрите. вы проверяете только делители < 100. этого недостаточно, чтобы доказать простоту того числа.

Вообще, во всех ваших программмах идет последовательный перебор нечетных делителей, а это сложность O(n) для каждого проверяемого числа. Это крайне неэффективно.

PS: -=ЮрА=-, зря вы так про справочники говорите, они помогают сократить время на написание программ, избегать глупых ошибок, неверных и неэффективных (в вашем случае) алгоритмов.
на основе вашей неприязни к справочникам могу предположить, что и библиотеками готовых алгоритмов вы не пользуетесь, и каждый раз всё пишете сначала. Мартышкин труд.
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 09:49 #44
Цитата Сообщение от ya_noob Посмотреть сообщение
вы хитрите. вы проверяете только делители < 100. этого недостаточно, чтобы доказать простоту того числа.
- я не хитрю я проверяю делители до 2^7 видимо стоит попробовать до 2^8 если бы кто-то в частности и вы

ya_noob, разбирались в математике то увидили бы что пробор от 2 до 11 позволяет рассматривать делители уже в интервале N/10 при этом не следует рассматривать все N/10 делителей, достаточно прогнать до половины разрядов N/10 (т.е до чисел квадрат которых даст порядок рассматриваемого числа) При этом надо ещё посмотреть а не лежат ли все элементарные делителе скажем в пределах 2^8. Я уже отметил до INT_MAX мой алгоритм весьма и весьма эффективен (это воочию показано на числе операций)
Цитата Сообщение от ya_noob Посмотреть сообщение
Вообще, во всех ваших программмах идет тупой последовательный перебор нечетных делителей, а это сложность O(n) для каждого проверяемого числа. Это крайне неэффективно.
- вот именно что если делители лежат до 2 в 8-й лучше просто их пробрать и секономить на итерациях (ведь чисел у которых делители 181 как на пост выше не так уж и много), т.е где то в 90% случаев совершив 5-10 итерайций я уже найду составное число, в то время как просев дает всегда 84 итерации на каждое число

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

Не по теме:

Цитата Сообщение от ya_noob Посмотреть сообщение
Позволю себе поучаствовать в этом безобразии, т.к. делать нечего.
- лучше займись своими делами

0
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 10:35 #45
Ternsip, ты ещё здесь?
Мы до сих пор разбирали мой алгоритм, верней то что на числах за INT_MAX он ещё не 100% точен, так вот давай лучше займёмся твоим(тебе даже за него + поставил ТС наивно полагая что ты действительно прав). Так вот давай поглядим что выдаст твой алгоритм на числе 2047 (делитель 23) и числе (3277 делитель 29) http://codepad.org/CMneLlht
Заметь по ссілке компипаст твоего кода (никаких моих ремарок)
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
 
using namespace std;
 
// big numbers
 
long mulmod(long a, long b, long MOD){
    if (b == 0) return 0;
    long res = mulmod(a, b >> 1, MOD);
    res += res;
    res %= MOD;
    return (b & 1)? (a + res) % MOD : res;
}
 
bool witness(long a, long n) {
    long d = 1;
    long b = n - 1;
    for(int i = 63; i >= 0; i--){
        if(b < pow(2.0, i)) continue;
        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 n, long tries) {
    for(int it = 0; it < tries; it++) {
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
 
// low numbers
 
#define forn(i, n) for(int i = 0; i < int(n); i++)
 
bool witnessLow(int a, int n) {
    int d = 1;
    int b = n - 1;
    for(int i = 31; i >= 0; i--) {
        if(b < (1 << i)) continue;
        int x = d;
        d = (long(d) * d) % n;
        if(d == 1 && x != 1 && x != n - 1) return true;
        if((b >> i) & 1) d = (long(d) * a) % n;
    }
    return (d != 1);
}
 
bool MillerRabinLow(int n) {
      if(n == 2) return true;
    if(witnessLow(2, n)) return false;
    return true;
}
 
bool test(long c){
    if (c < 1e9)
        return MillerRabinLow(c);
    else 
        return MillerRabin(c, 19);
}
 
int main()
{
        int arr[] = {2047, 3277};
 
    for(int i = 0; i < 2; i++)
    {
        cout<<arr[i]<<" - ";
        if(test(arr[i]))
            cout<<"SIMPLE"<<endl;
        else
            cout<<"NOT SIMPLE"<<endl;
    }
    return 0; 
}
Т.е уже 2 левых числа даже в первых 5-ти сотнях...
0
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
03.05.2013, 10:35
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2013, 10:35
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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