Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

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

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


Написал такой код:
Код:
#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 в 22:29.
fs444 вне форума   Ответить с цитированием
Старый 17.03.2010, 22:47   #2
Гром
Профессионал
 
Аватар для Гром
 
Регистрация: 21.03.2009
Сообщений: 2,193
Репутация: 473

icq: 482-373-277
По умолчанию

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

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

icq: 465033557
skype: Ozerich_
По умолчанию

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

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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


07:11.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.