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

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

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

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

21.07.2013, 16:52. Просмотров 2864. Ответов 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     Алгоритм нахождения простых чисел
Посмотрите здесь:

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

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

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

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

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

Написать программу нахождения первых 50 простых чисел - C++
Написать программу нахождения первых 50 простых чисел...Помогите пожалустно если можно то с коментариями!!

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 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
387 / 343 / 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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
21.07.2013, 17:41     Алгоритм нахождения простых чисел #9
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
А как же ручная оптимизация индукции "i*i<=n"?
как вы предлагаете это оптимизировать?

Добавлено через 1 минуту
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Почему никто ещё не посоветовал сделать табличку первых 6000 простых чисел?..
потому же, почему никто не посоветовал сделать прекалк на первый миллиард чисел.
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 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
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 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 Посмотреть сообщение
Я вообще в шутку это сказал, если что.
Я шутку понял, но доверия то не прибавилось всерьёз!

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.07.2013, 18:13     Алгоритм нахождения простых чисел
Еще ссылки по теме:

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

Эффективный алгоритм поиска простых чисел на С++ - C++
Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл который я добавил в функцию не работает....

Алгоритм перебора разных комбинаций простых чисел - C++
Доброго времени суток! Решаю разнообразные задачки по программированию, попалась вот такая: Определим функцию P(n,k) следующим...

Подскажите алгоритм подбора суммы простых чисел - C++
Задание такое - проверить возможно ли с помощью суммы 3 простых чисел составить любое число от 6 до 100. Задача решается только с помощью...

Жадный алгоритм нахождения абсолютной разницы чисел - C++
Вот мое задание: А вот мой код: #include &lt;cstdlib&gt; #include &lt;iostream&gt; #include &lt;stdio.h&gt; using namespace...


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

Или воспользуйтесь поиском по форуму:
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 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)
Yandex
Объявления
21.07.2013, 18:13     Алгоритм нахождения простых чисел
Ответ Создать тему
Опции темы

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