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

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

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

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

21.07.2013, 16:52. Просмотров 2860. Ответов 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++
Найти все трехзначные простые числа

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 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
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 10
Завершенные тесты: 1
21.07.2013, 18:38     Алгоритм нахождения простых чисел #17
Retyrn0, 155 - простое число?
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 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;
}
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 10
Завершенные тесты: 1
21.07.2013, 18:41     Алгоритм нахождения простых чисел #20
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Пардоньте, я знал, что википедии доверять нельзя
Неужели в Википедии так и говориться? Дай ссылку.
Точнее ссылку я нашел, а где там такое сказано - нет.
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
21.07.2013, 18:41     Алгоритм нахождения простых чисел #21
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c)
101
я уверен, имелись в виду числа до 100
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
21.07.2013, 18:42     Алгоритм нахождения простых чисел #22
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c)
это так и есть, но это не означает что любое число вида 6к+1, 6к-1 простое
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
21.07.2013, 19:01     Алгоритм нахождения простых чисел #23
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
я уверен, имелись в виду числа до 100
возможно имелось ввиду, но фразы "меньше 100" я не нашёл...

Цитата Сообщение от lazybiz Посмотреть сообщение
ссылку я нашел, а где там такое сказано - нет
ну как же? Листаете до пункта "Некоторые свойства", там 11 по счёту свойство =)

Добавлено через 1 минуту
Цитата Сообщение от aram_gyumri Посмотреть сообщение
это так и есть, но это не означает что любое число вида 6к+1, 6к-1 простое
Я осознал свою ошибку, прошу прощения)
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
21.07.2013, 19:02     Алгоритм нахождения простых чисел #24
Цитата Сообщение от Retyrn0 Посмотреть сообщение
возможно имелось ввиду, но фразы "меньше 100" я не нашёл...
не, пингвин прав. Тут логическая игра слов с толку немного сбивает.эта фраза аналогична "всякое простое число >3 не делится на 3". И это верно, в отличие от обратного утверждения.
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,737
21.07.2013, 19:12     Алгоритм нахождения простых чисел #25
Цитата Сообщение от salam Посмотреть сообщение
if(n & 1 == 0) return false;
число 2 покажет как не простое
добавить бы надо
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
21.07.2013, 20:53     Алгоритм нахождения простых чисел #26
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Тут логическая игра слов с толку немного сбивает.
учи матеметику кузя, это некакая не игра слов
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.07.2013, 20:59     Алгоритм нахождения простых чисел #27
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Нужно чтобы алгоритм был быстрым
Быстрая проверка натурального числа на простоту
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
22.07.2013, 05:34     Алгоритм нахождения простых чисел #28
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Пардоньте, я знал, что википедии доверять нельзя
не надо, пожалуйста, обвинять Википедию в ваших логических ошибках.
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2013, 08:34     Алгоритм нахождения простых чисел #29
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
C++
1
  if (n==1 || n==2 || n==3) return 1;

Не по теме:

1 - не простое число



Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
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)
такая оптимизация почти не заметна при тестировании чисел, скажем, от 1 до 10 000 000, выигрыш - сотые доли секунды. А вот если уменьшить количество лишних проверок, то можно скорость в разы увеличить.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.07.2013, 09:46     Алгоритм нахождения простых чисел
Еще ссылки по теме:

Алгоритм отбора простых чисел - 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...


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

Или воспользуйтесь поиском по форуму:
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
22.07.2013, 09:46     Алгоритм нахождения простых чисел #30
а можно же ведь использовать тест миллера-рабина да он не детерминированный зато работает быстро (за log3n), если память не изменяет то была задачка проверки на простоту чисел <264 и решалaсь она миллером-рабином
Yandex
Объявления
22.07.2013, 09:46     Алгоритм нахождения простых чисел
Ответ Создать тему
Опции темы

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