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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.87
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 11:41     Эффективный алгоритм поиска простых чисел на С++ #1
Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает. Можете подсказать почему??? Заранее спасибо.
Простое число - которое делится на 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для 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");
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 13:40  [ТС]     Эффективный алгоритм поиска простых чисел на С++ #3
Ternsip, Как написать примитивный вариант я знаю Мне не понятно почему в моей программе не работает цикл, подскажите??
P.S. Да, простое и составное число, перепутал.
Ternsip
 Аватар для 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);
}
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.
Я понимаю, что задаю наверное глупые и некорректные вопросы, но просто хочу разобраться.
Ternsip
 Аватар для 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 иначе
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 по которую идет цикл? Заранее спасибо.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 15:25     Эффективный алгоритм поиска простых чисел на С++ #8
Цитата Сообщение от NaikoN Посмотреть сообщение
и как переменная n которую Вы вводите связана с переменной a
в функцию я передаю переменную n, которая скопируется в "а"
это обычный цикл, не знаю как вам ещё объяснить...
-=ЮрА=-
Заблокирован
Автор 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;
}
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
NaikoN
2 / 2 / 0
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 16:04  [ТС]     Эффективный алгоритм поиска простых чисел на С++ #10
Ternsip, Число 27 составное, т.к. делится на 1,3,9,27.
Вы писали, что "в функцию я передаю переменную n, которая скопируется в "а"
это обычный цикл, не знаю как вам ещё объяснить... ", на основании чего число "n" скопируется в переменную а??
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 16:09     Эффективный алгоритм поиска простых чисел на С++ #11
NaikoN, да, про 27 ошибся

Добавлено через 1 минуту
NaikoN,
Цитата Сообщение от NaikoN Посмотреть сообщение
на основании чего число "n" скопируется в переменную а??
да на основании того, что вы передаёте переменную в аргументы функции, если вы передаёте не по ссылке, что вы и делаете, то вы просто скажете, что new int a = n;
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. Еще раз спасибо!!!
Ternsip
 Аватар для 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;
}
молодец, а я немного улучшил вашу функцию, она, практически, ничем не отличается.
-=ЮрА=-
Заблокирован
Автор 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;
}
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 16:48     Эффективный алгоритм поиска простых чисел на С++ #15
PS:Я не юзаю стандартные алгоритмы а пишу свои, причём краеугольным камнем в основе моих кодов лежит простота и доступность. Если я в чём то недоглядел, написал что неверно считает я и сам поправлю, т.к никогда никому лажу я не толкаю.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 16:50     Эффективный алгоритм поиска простых чисел на С++ #16
-=ЮрА=-, мне жалко вас расстраивать, но, увы, снова не верно, 221 = 17 * 13
-=ЮрА=-
02.05.2013, 16:51
  #17

Не по теме:

NaikoN, хорошо я основательно подумаю, чтобы код остался в пределах строк 30-35

Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 16:56     Эффективный алгоритм поиска простых чисел на С++ #18
-=ЮрА=-, 247 = 13*19

Добавлено через 30 секунд
-=ЮрА=-, да вот я уже 2 отличия привёл

Добавлено через 20 секунд
-=ЮрА=-, 169 221 247 289 299 323 361 377 391 403 437 481 493 527 529 533 551 559 589 611 629 667 689 697 703 713 731 767 779 793 799 817 841 851 871 вот отличия

Добавлено через 3 минуты
-=ЮрА=-, нужно проверять не до константы а до корня числа
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 17:19     Эффективный алгоритм поиска простых чисел на С++ #19
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
#include <cmath>
#include <iostream>
using namespace std;
 
bool isSimple(int num);
 
int main()
{
    int nCount  = 0;
    for(int num = 0; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
    }
    return 0;
}
 
bool isSimple(int num)
{
    int i;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        if( i != num )
            bSimple = num % i != 0;
    }
    for(i = 9 + 2; i <= num / 10 && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
    }
    return bSimple;
}

Не по теме:

ЗЫ:

Цитата Сообщение от Ternsip Посмотреть сообщение
-=ЮрА=-, нужно проверять не до константы а до корня числа
- у меня хватает мозгов написать свое, а не юзать чужие формулы.

Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.05.2013, 17:23     Эффективный алгоритм поиска простых чисел на С++
Еще ссылки по теме:

C++ функция поиска простых чисел
Алгоритм нахождения простых чисел C++
Алгоритм нахождения простых чисел C++

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

Или воспользуйтесь поиском по форуму:
-=ЮрА=-
Заблокирован
Автор FAQ
02.05.2013, 17:23     Эффективный алгоритм поиска простых чисел на С++ #20
Кому захочется проверять поштучно - модифицируем мэйн вот так
C++
1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    int nCount  = 0;
    for(int num = 0; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
        if( nCount && nCount % 40 == 0 )
            system("pause");
    }
    return 0;
}
Yandex
Объявления
02.05.2013, 17:23     Эффективный алгоритм поиска простых чисел на С++
Ответ Создать тему
Опции темы

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