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

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

Войти
Регистрация
Восстановить пароль
 
fs444
6 / 10 / 0
Регистрация: 18.08.2009
Сообщений: 480
17.03.2010, 21:27     граница проверки простого числа #1
У Дейтлов есть задача:


Написал такой код:
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
#include<iostream>
using namespace std;
 
#include<windows>
#include<cmath>
 
void prostoeChislo(int chislo);
 
int main()
{
     double chislo; //число, которое проверяется, простое оно или нет. В.п.
 
//   cout << "Vvedite chislo: " << endl;
//   cin >> chislo;
 
//   for (chislo = 1; chislo <= sqrt(10000.0); chislo++)
   for (chislo = 1; chislo <= (10000/2); chislo++)
   {
      prostoeChislo(chislo);
   }
 
   system("pause");
   return 0;
}
 
void prostoeChislo(int chislo)
{
   int status = 1; // 1 - простое, 2 - непростое
 
   if (chislo == 1)
   {
      status = 2;
   }
   else
   {
      for (int i = 2; i < chislo; i++)
      {
         if (chislo % i == 0)
         {
            status = 2;
         }
      }
   }
 
   if (status == 1)
   {
      cout << "Chislo " << chislo << " prostoe" << endl;
   }
   else if (status == 2)
   {
//      cout << "Chislo " << chislo << " NE prostoe" << endl;
   }
}
Вот они пишут, что при использовании sqrt() производительность выше, чем при n/2. Так ведь 10000 / 2 = 5000, а sqrt(10000) = 100. Получается, часть чисел теряется. Так?
Миниатюры
граница проверки простого числа  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.03.2010, 21:27     граница проверки простого числа
Посмотрите здесь:

C++ Определение простого числа
Бинарные числа! Перевод простого числа в бираное и расчет. C++
Функция для простого числа C++
Генерация случайного простого числа C++
C++ Номер минимального простого числа в массиве одномерном C++
C++ Поиск простого отрицательного числа
Генерация простого числа C++
C++ Генерация простого числа, заданной длины
Поиск простого числа C++
C++ поиск простого числа
C++ Определить функцию идентификации простого числа
C++ Поиск простого числа на примере с лямдой-выражением

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
17.03.2010, 22:24     граница проверки простого числа #2
Ничего не теряется.
Это просто математика.
Допустим мы проверяем число 10000 и у нас есть минимальный делитель 200.
Но если у нас есть делитель 200, тогда 10000/200 = 50
и 50 тоже делитель.
Но 50<200, значит мы получили меньший делитель, что противоречит условию.
Следовательно у нас не может быть минимального делителя 200.
Следовательно нет смысла проверять до 200.

Максимальное число до которого нужно проверять - это sqrt(10000) = 100
fs444
6 / 10 / 0
Регистрация: 18.08.2009
Сообщений: 480
22.03.2010, 21:57  [ТС]     граница проверки простого числа #3
odip, понятно, спасибо =)
Yandex
Объявления
22.03.2010, 21:57     граница проверки простого числа
Ответ Создать тему
Опции темы

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