Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.63/51: Рейтинг темы: голосов - 51, средняя оценка - 4.63
2 / 2 / 1
Регистрация: 01.05.2013
Сообщений: 109
1

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

02.05.2013, 11:41. Просмотров 10447. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.05.2013, 11:41
Ответы с готовыми решениями:

Алгоритм поиска простых чисел
Доброго времени суток. Помогите пожалуйста с алгоритмом поиска простых чисел в массиве. Искал...

Алгоритм поиска n простых чисел
Помогите, пожалуйста, составить батник, находящий простые числа в заданном интервале.

Алгоритм поиска простых чисел.
Нашел пример алгоритма, используемого для получения всех простых чисел от 2 до заданного путем...

Реализовать алгоритм поиска простых чисел
Реализовать алгоритм поиска простых чисел (&quot;Решето Эратосфена&quot;) до 200. Подскажите как плиз

94
667 / 195 / 29
Регистрация: 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
2 / 2 / 1
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 13:40  [ТС] 3
Ternsip, Как написать примитивный вариант я знаю Мне не понятно почему в моей программе не работает цикл, подскажите??
P.S. Да, простое и составное число, перепутал.
0
667 / 195 / 29
Регистрация: 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
2 / 2 / 1
Регистрация: 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
667 / 195 / 29
Регистрация: 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
2 / 2 / 1
Регистрация: 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
667 / 195 / 29
Регистрация: 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
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
2 / 2 / 1
Регистрация: 01.05.2013
Сообщений: 109
02.05.2013, 16:04  [ТС] 10
Ternsip, Число 27 составное, т.к. делится на 1,3,9,27.
Вы писали, что "в функцию я передаю переменную n, которая скопируется в "а"
это обычный цикл, не знаю как вам ещё объяснить... ", на основании чего число "n" скопируется в переменную а??
0
667 / 195 / 29
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 16:09 11
NaikoN, да, про 27 ошибся

Добавлено через 1 минуту
NaikoN,
Цитата Сообщение от NaikoN Посмотреть сообщение
на основании чего число "n" скопируется в переменную а??
да на основании того, что вы передаёте переменную в аргументы функции, если вы передаёте не по ссылке, что вы и делаете, то вы просто скажете, что new int a = n;
1
2 / 2 / 1
Регистрация: 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
667 / 195 / 29
Регистрация: 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
667 / 195 / 29
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 16:50 16
-=ЮрА=-, мне жалко вас расстраивать, но, увы, снова не верно, 221 = 17 * 13
0
-=ЮрА=-
02.05.2013, 16:51
  #17

Не по теме:

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

0
667 / 195 / 29
Регистрация: 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 минуты
-=ЮрА=-, нужно проверять не до константы а до корня числа
0
Заблокирован
Автор 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 Посмотреть сообщение
-=ЮрА=-, нужно проверять не до константы а до корня числа
- у меня хватает мозгов написать свое, а не юзать чужие формулы.

1
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
Заблокирован
Автор 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;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.05.2013, 17:23

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Cоставить алгоритм поиска N простых чисел
составить алгоритм поиска N простых чисел

Алгоритм поиска целых простых чисел
Предлагаю простой алгоритм проверки и поиска простых чисел, приглашаю к сотрудничеству в написании...

Линейный алгоритм поиска простых чисел
Здравствуйте, помогите пожалуйста написать линейный алгоритм на языке си, желательно с...

Алгоритм поиска количества простых чисел в заданном массиве
алгоритм поиск количества простых чисел в заданном целочисленном массиве из 50 элементов. Помогите...


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

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

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