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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.68
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
#1

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

21.07.2013, 16:52. Просмотров 2725. Ответов 38
Метки нет (Все метки)

Вопросы:
1) Нужен алгоритм проверки числа (является ли число простим). Нужно чтобы алгоритм был быстрым (нужно проделать 104 операций за 0.5 сек )!!!!
2) Почему мой алгоритм проверки не всегда дает верный ответ?

C++
1
if(x%2 && x%3 && x%5 && x%7) std::cout << "Число простое!\n";
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.07.2013, 16:52     Алгоритм нахождения простых чисел
Посмотрите здесь:

Написать программу нахождения первых 50 простых чисел C++
C++ Алгоритм нахождения ПРОСТЫХ чисел в файле
Алгоритм нахождения простых чисел C++
Эффективный алгоритм поиска простых чисел на С++ C++
C++ Напишите программу нахождения всех трехзначных простых чисел
C++ Нахождения больших простых чисел
C++ Подскажите алгоритм подбора суммы простых чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.07.2013, 17:01     Алгоритм нахождения простых чисел #2
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Нужно чтобы алгоритм был быстрым (нужно проделать 109 операций за 0.5 сек )
че за хрень вы несете?
2) предположу, что у некоторых чисел могут быть другие делители, кроме этих 4. что касается вашего алгоритма, он назовет "простыми" как раз только составные числа.

Добавлено через 2 минуты
если речь шла о том, чтобы проверить 104 чисел, то при определенных ограничениях и обычный n*sqrt(n) зайдет.
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
21.07.2013, 17:11  [ТС]     Алгоритм нахождения простых чисел #3
Цитата Сообщение от salam Посмотреть сообщение
обычный n*sqrt(n) зайдет
Можно кусок кода (алгоритм)!!!
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
21.07.2013, 17:26     Алгоритм нахождения простых чисел #4
C++
1
2
3
4
5
6
7
8
9
10
int is_prime(int n){
  int i=3;
  if(!n&1) return 0;
  if (n==1 || n==2 || n==3) return 1;
  do{
    if(n%i) return 0;
    i+=2;
  }while(i*i<=n);
  return 1;
}
dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
21.07.2013, 17:29     Алгоритм нахождения простых чисел #5
Kuzia domovenok, и что по твоему код рабочий?
http://codepad.org/yFCxb3JO
OhMyGodSoLong
21.07.2013, 17:35
  #6

Не по теме:

Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
n&1

n==1 || n==2 || n==3
А как же ручная оптимизация индукции "i*i<=n"? А то вдруг компилятор вставит умножение?!

salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.07.2013, 17:38     Алгоритм нахождения простых чисел #7
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Можно кусок кода (алгоритм)!!!
категорически от вас требуется, чтобы проверка каждого числа на простоту выполнялась за корень. это выглядит так:
C++
1
2
3
4
5
6
bool _isprime(int n) {
   for(int i=2; i*i <= n; ++i)
      if(n % i == 0)
         return false;
   return true;
}
далее вы можете применять любые эвристики. самая очевидная: проверять только нечетные делители. практически целесообразно отсекать пару частых делителей. короче говоря, можно прийти к такому:

C++
1
2
3
4
5
6
7
bool _isprime(int n) {
   if(n & 1 == 0) return false;
   for(int i=3; i*i <= n; i += 2)
      if(n % i == 0)
         return false;
   return true;
}
Добавлено через 2 минуты
асимптотически, алгоритмы совершенно одинаковы, но в среднем второй должен работать в два раза быстрее.
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
21.07.2013, 17:38     Алгоритм нахождения простых чисел #8
Почему никто ещё не посоветовал сделать табличку первых 6000 простых чисел?..
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.07.2013, 17:41     Алгоритм нахождения простых чисел #9
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
А как же ручная оптимизация индукции "i*i<=n"?
как вы предлагаете это оптимизировать?

Добавлено через 1 минуту
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Почему никто ещё не посоветовал сделать табличку первых 6000 простых чисел?..
потому же, почему никто не посоветовал сделать прекалк на первый миллиард чисел.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
21.07.2013, 17:41     Алгоритм нахождения простых чисел #10
Цитата Сообщение от aram_gyumri Посмотреть сообщение
Kuzia domovenok, и что по твоему код рабочий?
http://codepad.org/yFCxb3JO
А? Что? э... Конечно!
http://codepad.org/pfuUgwLP
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int is_prime(unsigned int n){
  int i=1;
  if(!(n&1)) return 0;
  if (n==1 || n==2 || n==3) return 1;
  do{
    i+=2;
    if(!(n%i)) return 0;
  }while(i*i<=n);
  return 1;
}
int main(){
  printf(is_prime(5)?"prime":"not prime");
  return 0;
}
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
21.07.2013, 17:44     Алгоритм нахождения простых чисел #11
Цитата Сообщение от salam Посмотреть сообщение
как вы предлагаете это оптимизировать?
C++
1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 3; i*i <= n; i += 2)
 
||
\/
 
for (int i = 3, i_sq = 9; i_sq <= n; i_sq += (i + 1) << 2, i += 2)
 
||
\/
 
int n_sqrt = sqrt(n);
for (int i = 3; i <= n_sqrt; i += 2)
НИКОГДА НЕ ДОВЕРЯЙ КОМПИЛЯТОРУ! ВСЁ НАДО ОПТИМИЗИРОВАТЬ РУКАМИ! SSE-ИНСТРУКЦИЙ ТОЖЕ НЕ СУЩЕСТВУЕТ!

Извините.

Цитата Сообщение от salam Посмотреть сообщение
потому же, почему никто не посоветовал сделать прекалк на первый миллиард чисел.
Миллиард это много. А вот первые 6000 вполне влезут в кеш.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
21.07.2013, 17:51     Алгоритм нахождения простых чисел #12
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
for (int i = 3, i_sq = 9; i_sq <= n; i_sq += (i + 1) << 2, i += 2)
Об этом я, кстати задумывался, как об альтернативе i*i, но решил, что выигрыш скорости не будет существеннен.
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
int n_sqrt = sqrt(n);
for (int i = 3; i <= n_sqrt; i += 2)
а как же оптимизация sqrt?

Добавлено через 39 секунд
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
НИКОГДА НЕ ДОВЕРЯЙ КОМПИЛЯТОРУ! ВСЁ НАДО ОПТИМИЗИРОВАТЬ РУКАМИ! SSE-ИНСТРУКЦИЙ ТОЖЕ НЕ СУЩЕСТВУЕТ!
Я это как раз понимаю, потому и не доверяю. А что такое SSE?
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
21.07.2013, 17:52     Алгоритм нахождения простых чисел #13
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
а как же оптимизация sqrt?
1. Она вызывается один раз.
2. Я уверен, что алгоритм Ньютона в стандартной библиотеке и так заоптимизирован донельзя.

Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Я это как раз понимаю, потому и не доверяю. А что такое SSE?
Я вообще в шутку это сказал, если что.

SSE — это то, что позволяет выполнять по четыре деления за один раз, что затыкает за пояс все эти "& 1" и прочее.
Kuzia domovenok
21.07.2013, 17:55
  #14

Не по теме:

Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Я вообще в шутку это сказал, если что.
Я шутку понял, но доверия то не прибавилось всерьёз!

castaway
Эксперт С++
4876 / 3015 / 370
Регистрация: 10.11.2010
Сообщений: 11,075
Записей в блоге: 10
Завершенные тесты: 1
21.07.2013, 18:13     Алгоритм нахождения простых чисел #15
Нашел на StackOverflow и внес незначительные изменения. ( http://stackoverflow.com/questions/4...umber-is-prime )
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
#include <iostream>
#include <chrono>
 
using namespace std;
 
__int64 power( int a, int n, int mod )
{
    __int64 power = a, result = 1;
    while ( n ) {
        if ( n & 1 ) result = (result * power) % mod;
        power = (power * power) % mod;
        n >>= 1;
    }
    return result;
}
 
bool witness( int a, int n )
{
    int t,u,i;
    __int64 prev,curr;
 
    u = n >> 1;
    t = 1;
 
    while ( !(u & 1) ) {
        u >>= 1;
        ++t;
    }
 
    prev = power( a, u, n );
    for ( i = 1; i <= t; ++i ) {
        curr = (prev * prev) % n;
        if ( (curr == 1) && (prev != 1) && (prev != n - 1) ) return true;
        prev = curr;
    }
    if ( curr != 1 ) return true;
    return false;
}
 
inline bool IsPrime( int number )
{
    if ( ((!(number & 1)) && number != 2) || (number < 2) || (number % 3 == 0 && number != 3) ) return false;
 
    if ( number < 1373653 ) {
        for( int k = 1; 36 * k * k - 12 * k < number; ++k )
            if ( (number % (6 * k + 1) == 0) || (number % (6 * k - 1) == 0) )
                return false;
        return true;
    }
 
    if ( number < 9080191 ) {
        if ( witness( 31, number ) ) return false;
        if ( witness( 73, number ) ) return false;
        return true;
    }
 
    if ( witness(  2, number ) ) return false;
    if ( witness(  7, number ) ) return false;
    if ( witness( 61, number ) ) return false;
    return true;
}
 
int main()
{
    chrono::system_clock::time_point a = chrono::system_clock::now();
    for ( unsigned int i = 0; i < 1000000; i++ ) {
        if ( IsPrime( i ) ) {
            cout << i << endl;
        }
    }
    chrono::system_clock::time_point b = chrono::system_clock::now();
    cout << chrono::duration_cast< chrono::milliseconds >( b - a ).count() << " ms.\n";
    return 0;
}
Среди чисел от 0 до 1 000 000 находит простые ~ за 386 ms. Ноутбук с Core i3, MinGW 4.7.3 (32 бита), ключ оптимизации -O0 (т.е. отключена)

Добавлено через 7 минут
Без вывода ~ 132 ms. (уже на MinGW 4.8.1)
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
21.07.2013, 18:37     Алгоритм нахождения простых чисел #16
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
void main()
{
    int x;
    while(1)
    {
        printf("Vvedite chislo: ");
        scanf("%d",&x);
        system("cls");
        if(x==1 || x==2 || x==3 || (x-1)%6==0 || (x+1)%6==0)printf("Chislko %d - Naturalnoye!\n",x);
        else printf("Chislko %d - Ne naturalnoye!\n",x);
    }
}
ИМХО, вариант наиболее быстрый и вытекает из свойства простых чисел:

Всякое простое число, большее 3, представимо в виде или , где — некоторое натуральное число.(с)Википедия

Добавлено через 53 секунды
конечно бесконечный цикл нужно убрать по-хорошему )

Добавлено через 2 минуты
Выпали формулы =/
http://ru.wikipedia.org/wiki/Простое_число, там в разделе "Некоторые свойства" русским по белому написано это свойство натуральных чисел.
castaway
Эксперт С++
4876 / 3015 / 370
Регистрация: 10.11.2010
Сообщений: 11,075
Записей в блоге: 10
Завершенные тесты: 1
21.07.2013, 18:38     Алгоритм нахождения простых чисел #17
Retyrn0, 155 - простое число?
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
21.07.2013, 18:39     Алгоритм нахождения простых чисел #18
Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c)

Добавлено через 1 минуту
Цитата Сообщение от lazybiz Посмотреть сообщение
155 - простое число
Пардоньте, я знал, что википедии доверять нельзя
soican
49 / 23 / 1
Регистрация: 16.11.2011
Сообщений: 329
Записей в блоге: 5
21.07.2013, 18:41     Алгоритм нахождения простых чисел #19
вот, кое что было - игрался с С++11
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
 
using namespace std;
using namespace std::placeholders;
 
std::vector<int>simple_numbers(1,2); // перевое простое число 2
bool check_for_simple_numbers (int i, int x)
 {  return (x%i);}
 
 void finding_simple_numbers(int x)
 { for (int i = 3; i <= x; i+=2) // чётные числа нет смысла проверять
     { auto f = bind(check_for_simple_numbers, _1, i);
       if ( std::all_of( simple_numbers.begin(), simple_numbers.end(), f) )
          simple_numbers.push_back(i);
    }
 }
int main()
{   int x;
    cout << "Type number, all simple numbers before you want to be detected  \n";
    cin >> x;
 
 finding_simple_numbers(x);
 
 for ( auto i: simple_numbers)
     { std::cout << i <<" "; }
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.07.2013, 18:41     Алгоритм нахождения простых чисел
Еще ссылки по теме:

Жадный алгоритм нахождения абсолютной разницы чисел C++
Написать алгоритм нахождения наибольшего общего делителя трех чисел C++
Программа нахождения простых чисел C++
C++ Алгоритм перебора разных комбинаций простых чисел
C++ Алгоритм отбора простых чисел

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

Или воспользуйтесь поиском по форуму:
castaway
Эксперт С++
4876 / 3015 / 370
Регистрация: 10.11.2010
Сообщений: 11,075
Записей в блоге: 10
Завершенные тесты: 1
21.07.2013, 18:41     Алгоритм нахождения простых чисел #20
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Пардоньте, я знал, что википедии доверять нельзя
Неужели в Википедии так и говориться? Дай ссылку.
Точнее ссылку я нашел, а где там такое сказано - нет.
Yandex
Объявления
21.07.2013, 18:41     Алгоритм нахождения простых чисел
Ответ Создать тему
Опции темы

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