Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Образовательный студенческий форум _ Информатика / Программирование _ Проверка чисел на простоту
Автор: Sergio Ramos 28.4.2011, 12:26
Код
#include "iostream"
#include "vector"
using namespace std;
int f(int n) {
vector<char> prime (n+1, true);
prime[0] = prime[1] = false;
for (int i=2; i<=n; ++i)
if (prime[i])
for (int j=i*i; j<=n; j+=i)
prime[j] = false;
return prime[n];}
int main () {
int n;
cin >> n;
int *a=new int [n];
for (int i=0;i<n;i++) {cin >> a[i];
if (f(a[i])) cout << "YES" << endl; else cout << "NO" << endl;}
return 0;}
#include "vector"
using namespace std;
int f(int n) {
vector<char> prime (n+1, true);
prime[0] = prime[1] = false;
for (int i=2; i<=n; ++i)
if (prime[i])
for (int j=i*i; j<=n; j+=i)
prime[j] = false;
return prime[n];}
int main () {
int n;
cin >> n;
int *a=new int [n];
for (int i=0;i<n;i++) {cin >> a[i];
if (f(a[i])) cout << "YES" << endl; else cout << "NO" << endl;}
return 0;}
Числа в диапазоне от 1 до 10^9. По времени работает нормально, но, я так понимаю, на слишком больших числах использует много памяти. Как можно переделать?
Автор: Vahappaday 28.4.2011, 15:32
не совсем понял логику того, что происходит в f().
Я бы сделал так:
1. Считать n чисел.
2. Найти максимальное.
3. Найти все простые до sqrt(n), записав их в массив.
4. Поочередно смотреть остаток от деления всех пользовательских чисел на все найденные простые. Если хотя бы в одном случае остаток 0 - число не простое, иначе - простое.
Попробуйте сами код, если что - помогу.
Автор: Sergio Ramos 28.4.2011, 16:34
Цитата(Vahappaday @ 28.4.2011, 15:32) 
не совсем понял логику того, что происходит в f().
Решето Эратосфена
Была такая идея, но проблема в построении ряда простых чисел, меньших sqrt[max(n)]
Почитал про http://e-maxx.ru/algo/bpsw, он достаточно объемный, потому что проверяет кучу условий. но работает нормально. задачу сделал
Автор: Vahappaday 28.4.2011, 16:38
хм)) интересный, не видел раньше) спасибо)
Русская версия Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)