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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.86
Ramos08
0 / 0 / 0
Регистрация: 25.04.2011
Сообщений: 5
#1

Проверка чисел на простоту - C++

25.04.2011, 21:40. Просмотров 3732. Ответов 7
Метки нет (Все метки)

сам код
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
#include "stdafx.h"
#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;}
Числа в интервале от 1 до 10^9.
Необходимо увеличить быстродействие. Я так понимаю, что-то неладное с большими числами
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2011, 21:40     Проверка чисел на простоту
Посмотрите здесь:

[Cи] Проверка чисел на простоту - C++
Как в Си написать программу, которая проверяла бы вводимые числа на простоту вероятностными методами. Числа поряка 10^5000---10^20000 за...

Проверка чисел на простоту и проверку на наличие общих цифр в записи - C++
Помогите написать программу: Для каждого (n) из некоторого количества натуральных чисел указать простое число К, ближайшее к числу n и...

Проверка числа на простоту - C++
Написать программу, которая запрашивает массив натуральных чисел (ввод с клавиатуры), а затем выводит на экран те элементы массива, которые...

Проверка числа на простоту - C++
Дано натуральное число n&gt;1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число...

Проверка числа на простоту - C++
Почему, если необ. проверить, является ли число простым(напр. ч-ло n),можно просматривать делители не от 2 до n, а от 2 до sqrt(n)? P.S....

Проверка числа на простоту - C++
Дано натуральное число N, проверить, простое оно или нет. Увеличить его значение на натуральное число M. Проверить, осталось ли оно ...

Проверка числа на простоту - C++
Помогите решить 2 задачки, пожалуйста, 1. Написать программу для проверки натурального числа N на простоту. N вводится с клавиатуры. ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ramos08
0 / 0 / 0
Регистрация: 25.04.2011
Сообщений: 5
28.04.2011, 16:22  [ТС]     Проверка чисел на простоту #2
Есть предложения?
kazak
3034 / 2355 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
29.04.2011, 08:55     Проверка чисел на простоту #3
В функции проверки в первом цикле i надо сравнивать с округленным корнем квадратным из n. В вашем же варианте большую часть времени цикл будет работать в пустую. И вообще непонятно зачем сдесь чаровский вектор, если заменить работу с ним на обычное нахождение остатка от деления, к улучшенному быстродействию можно еще получить и экономию памяти (довольно значительную при больших числах).
olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
29.04.2011, 11:31     Проверка чисел на простоту #4
щас напишем))

Добавлено через 15 минут
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
#include <iostream> 
#include <cmath> 
 
int prost(int x)
 {   if (x==2) return 1;
     if (x==0||x==1||x%2==0) return 0;
     for (int i=3; i<sqrt((float)x); i+=2)
        if (x/i==0) return 0;
        return 1;
 }
 
void main ()
{ int *A,N;
std::cout<<"Input N ";
std::cin>>N;
A=new int [N];
for (int i=0; i<N; i++)
    {   std::cout<<"A["<<i<<"]"<<std::endl;
        std::cin>>A[i];
        if (prost(A[i])) std::cout<<"yes"<<std::endl;
        else std::cout<<"no"<<std::endl;
    }
system ("pause");
}
kazak
3034 / 2355 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
29.04.2011, 12:00     Проверка чисел на простоту #5
olleg90, вы свою программу хотя бы компилировали?

Добавлено через 17 минут
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
#include <iostream>
#include <cmath>
 
bool isPrime(unsigned int number)
{
   if (number < 2)
      return 0;
   unsigned int root = static_cast<unsigned int>(std::sqrt(static_cast<double>(number)));
   for (int i = 2; i <= root; i++)
      if ((number % i) == 0)
         return 0;
   return 1;
}
 
int main(int argc, char* argv[])
{
   unsigned int size, num;
 
   std::cout << "Ââåäèòå êîëè÷åñòâî Г·ГЁГ±ГҐГ«: ";
   std::cin >> size;
 
   for (int i = 0; i < size; i++)
   {
 
      std::cout << "Ââåäèòå ÷èñëî: ";
      std::cin >> num;
      if (isPrime(num))
         std::cout << "×èñëî " << num << " ïðîñòîå." << std::endl;
      else
         std::cout << "×èñëî " << num << " ñîñòГ*ГўГ*îå." << std::endl;
   }
   std::system("pause");
   return 0;
}
olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
29.04.2011, 13:04     Проверка чисел на простоту #6
Цитата Сообщение от kazak Посмотреть сообщение
olleg90, вы свою программу хотя бы компилировали?
да! а в чем проблема?
Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
29.04.2011, 13:09     Проверка чисел на простоту #7
Алгоритм, если мне не изменяет память, называется решето Эратосфена. Для его реализации лучше подойдет битсет. По вопросу реализации - индусский подход, зачем для каждого числа пересчитывать полный набор чисел? Числа пропускаются через решето только один раз, а потом просто проверяется значение по индексу выбранного числа.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2011, 13:10     Проверка чисел на простоту
Еще ссылки по теме:

Проверка на простоту числа - C++
как мне сделать так, чтобы узнать простое является число или составное, не через bool, а как-нибудь через оператор switch case: т е, case...

Проверка числа на простоту - C++
я реализовал вот так, но алгоритм очень долгий, мне надо проверять очень большое количество чисел (десятки тысяч) и он так надолго виснет...

Проверка числа на простоту - C++
Помогите написать программу которая проверяет простое число или нет.

Проверка номера элемента массива на простоту - C++
Дан массив вещественных чисел.Необходимо вывести сумму чисел, порядковые номера которых являются простыми числами. Как можно осуществить...

Проверка числа на простоту (нужны комментарии) - C++
объясните пожалуйста, как в данной функции выполняется проверка числа на простоту. как можно поподробнее bool Prime(int const num)//...


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

Или воспользуйтесь поиском по форуму:
olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
29.04.2011, 13:10     Проверка чисел на простоту #8
я согласен что в строке
C++
1
if (x==0||x==1||x%2==0) return 0;
лучше написать так
C++
1
if (x<2||x%2==0) return 0;
а так все норм
Yandex
Объявления
29.04.2011, 13:10     Проверка чисел на простоту
Ответ Создать тему
Опции темы

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