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

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

02.05.2013, 11:41. Просмотров 6701. Ответов 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;
}

http://www.cyberforum.ru/cpp-beginners/thread2108343.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2013, 11:41
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Эффективный алгоритм поиска простых чисел на С++ (C++):

Эффективный алгоритм для поиска минимума в массиве
В массиве X(N) найти значения двух наименьших элементов и вывести их в порядке...

функция поиска простых чисел
не могу сделать функции для поиска простых чисел, вот код функции int...

Программа поиска простых чисел
Необходимо написать программу для поиска простых чесил в интервале от 1 до 100...

Функция для поиска ближайших простых чисел
Ув. товарищи программисты , нужна помощь. Требуется функция с помощью которой...

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

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

Добавлено через 1 минуту
NaikoN,
Цитата Сообщение от NaikoN Посмотреть сообщение
на основании чего число "n" скопируется в переменную а??
да на основании того, что вы передаёте переменную в аргументы функции, если вы передаёте не по ссылке, что вы и делаете, то вы просто скажете, что new int a = n;
1
NaikoN
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
Ternsip
663 / 191 / 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
Ternsip
663 / 191 / 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
Ternsip
663 / 191 / 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
02.05.2013, 17:23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.05.2013, 17:23
Привет! Вот еще темы с решениями:

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

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

Алгоритм нахождения простых чисел
Вопросы: 1) Нужен алгоритм проверки числа (является ли число простим). Нужно...

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


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

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

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