Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.03.2010, 21:27   #1
fs444
Форумчанин
 
Регистрация: 18.08.2009
Сообщений: 289
По умолчанию граница проверки простого числа

У Дейтлов есть задача:


Написал такой код:
Код:
#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. Получается, часть чисел теряется. Так?

Последний раз редактировалось fs444; 17.03.2010 в 21:29.
fs444 вне форума Ответить с цитированием
Старый 17.03.2010, 21:47   #2
Гром
Старожил
 
Аватар для Гром
 
Регистрация: 21.03.2009
Сообщений: 2,193
По умолчанию

Если число n (sqrt(n) = m) делится на x > m, то y = n / x будет y < m. Соответственно, если число не простое, то существование делителя было найдено еще раньше, чем дошли до x.
Простые и красивые программы - коды программ + учебник C++
Создание игры - взгляд изнутри - сайт проекта
Тема на форуме, посвященная ему же
Гром вне форума Ответить с цитированием
Старый 22.03.2010, 21:57   #3
fs444
Форумчанин
 
Регистрация: 18.08.2009
Сообщений: 289
По умолчанию

А как понимать запись "n (sqrt(n) = m)"?
fs444 вне форума Ответить с цитированием
Старый 22.03.2010, 22:07   #4
Ozerich
Студент 1 курса
Форумчанин Подтвердите свой е-майл
 
Аватар для Ozerich
 
Регистрация: 27.06.2008
Сообщений: 959
По умолчанию

Короче, у числа N нету делителей, больше чем sqrt(N), т.е корень из N
C++(STL, QT, WinInet) / DHTML(CSS) / JavaScript / PHP Developer
Ozerich вне форума Ответить с цитированием
Старый 24.03.2010, 20:11   #5
fs444
Форумчанин
 
Регистрация: 18.08.2009
Сообщений: 289
По умолчанию

Ага, ясно, спасибо.
fs444 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
TICQClient создание простого клиента betirsolt Работа с сетью в Delphi 7 19.02.2010 17:43
[C] Нахождение наибольшего простого пути wolfram Помощь студентам 0 29.11.2009 12:33
Помогите написать скрипт для проверки правильности ввода числа в строке DiSpalL JavaScript, Ajax 6 19.06.2009 16:48
MTanks - проще простого Dux Gamedev - cоздание игр: Unity, OpenGL, DirectX 0 15.06.2008 00:58