Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

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

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

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

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

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

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

38
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/Простое_число, там в разделе "Некоторые свойства" русским по белому написано это свойство натуральных чисел.
0
castaway
Эксперт С++
4887 / 3022 / 370
Регистрация: 10.11.2010
Сообщений: 11,080
Записей в блоге: 10
Завершенные тесты: 1
21.07.2013, 18:38 #17
Retyrn0, 155 - простое число?
0
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 - простое число
Пардоньте, я знал, что википедии доверять нельзя
0
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;
}
0
castaway
Эксперт С++
4887 / 3022 / 370
Регистрация: 10.11.2010
Сообщений: 11,080
Записей в блоге: 10
Завершенные тесты: 1
21.07.2013, 18:41 #20
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Пардоньте, я знал, что википедии доверять нельзя
Неужели в Википедии так и говориться? Дай ссылку.
Точнее ссылку я нашел, а где там такое сказано - нет.
0
Kuzia domovenok
1948 / 1801 / 137
Регистрация: 25.03.2012
Сообщений: 6,238
Записей в блоге: 1
21.07.2013, 18:41 #21
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c)
101
я уверен, имелись в виду числа до 100
0
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
21.07.2013, 18:42 #22
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Всякое простое число, большее 3, представимо в виде 6k+1 или 6k-1, где k — некоторое натуральное число.(c)
это так и есть, но это не означает что любое число вида 6к+1, 6к-1 простое
2
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 простое
Я осознал свою ошибку, прошу прощения)
1
Kuzia domovenok
1948 / 1801 / 137
Регистрация: 25.03.2012
Сообщений: 6,238
Записей в блоге: 1
21.07.2013, 19:02 #24
Цитата Сообщение от Retyrn0 Посмотреть сообщение
возможно имелось ввиду, но фразы "меньше 100" я не нашёл...
не, пингвин прав. Тут логическая игра слов с толку немного сбивает.эта фраза аналогична "всякое простое число >3 не делится на 3". И это верно, в отличие от обратного утверждения.
0
ValeryS
Модератор
6705 / 5114 / 482
Регистрация: 14.02.2011
Сообщений: 17,183
21.07.2013, 19:12 #25
Цитата Сообщение от salam Посмотреть сообщение
if(n & 1 == 0) return false;
число 2 покажет как не простое
добавить бы надо
0
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
21.07.2013, 20:53 #26
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Тут логическая игра слов с толку немного сбивает.
учи матеметику кузя, это некакая не игра слов
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.07.2013, 20:59 #27
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Нужно чтобы алгоритм был быстрым
Быстрая проверка натурального числа на простоту
0
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 748
22.07.2013, 05:34 #28
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Пардоньте, я знал, что википедии доверять нельзя
не надо, пожалуйста, обвинять Википедию в ваших логических ошибках.
0
Thinker
Эксперт С++
4228 / 2202 / 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, выигрыш - сотые доли секунды. А вот если уменьшить количество лишних проверок, то можно скорость в разы увеличить.
0
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
22.07.2013, 09:46 #30
а можно же ведь использовать тест миллера-рабина да он не детерминированный зато работает быстро (за log3n), если память не изменяет то была задачка проверки на простоту чисел <264 и решалaсь она миллером-рабином
0
22.07.2013, 09:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.07.2013, 09:46
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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