Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
9 / 13 / 3
Регистрация: 18.08.2009
Сообщений: 487

Граница проверки простого числа

17.03.2010, 21:27. Показов 1111. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
У Дейтлов есть задача:


Написал такой код:
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. Получается, часть чисел теряется. Так?
Миниатюры
Граница проверки простого числа  
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
17.03.2010, 21:27
Ответы с готовыми решениями:

Рекурсивная функция проверки простого числа
Не могу разобраться !! Как она вставляет в код без рекурсива?! Прошу помощи вставте эту долбанную...

Бинарные числа! Перевод простого числа в бираное и расчет.
Здравствуйте!Я понимаю, что моя просьба банальна, но я правда не могу никак разобраться с бинарными...

Структура элемента массива игрушка: название, цена, цвет, возрастной диапазон - нижняя граница, верхняя граница
Структура элемента массива игрушка: название, цена, цвет, возрастной диапазон - нижняя граница,...

2
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
17.03.2010, 22:24
Ничего не теряется.
Это просто математика.
Допустим мы проверяем число 10000 и у нас есть минимальный делитель 200.
Но если у нас есть делитель 200, тогда 10000/200 = 50
и 50 тоже делитель.
Но 50<200, значит мы получили меньший делитель, что противоречит условию.
Следовательно у нас не может быть минимального делителя 200.
Следовательно нет смысла проверять до 200.

Максимальное число до которого нужно проверять - это sqrt(10000) = 100
0
9 / 13 / 3
Регистрация: 18.08.2009
Сообщений: 487
22.03.2010, 21:57  [ТС]
odip, понятно, спасибо =)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
22.03.2010, 21:57
Помогаю со студенческими работами здесь

Найти все простые числа, меньше данного числа N. Определение простого числа описать в функции
Найти все простые числа, меньше данного числа N. Определение простого числа описать в функции

Составить программу вычисления наименьшего простого числа, большего заданного числа M (М>1)
Составить программу вычисления наименьшего простого числа, большего заданного числа M (М&gt;1)

Для каждого числа n выведите показатель n-го по порядку простого числа Мерсенна
(Если число 2n - 1 простое, то его называют числом Мерсенна.) В первой строке дано число m (1 &lt;= m...

Составить программу вычисления наименьшего простого числа, большего заданного числа M (М>1)
вычисления наименьшего простого числа, большего заданного числа M (М&gt;1).

Есть ли в последовательности числа-близнецы (использовать процедуру определения простого числа)
Дана N натуральное число. между n,n+1,..,2n числами близнец числа, то есть, надо определить есть ли...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
Вывод данных через динамический список в справочнике
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа
Maks 01.04.2026
Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .
К слову об оптимизации
kumehtar 01.04.2026
Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр).
Hrethgir 31.03.2026
Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда
anaschu 31.03.2026
В прикрепленном документе раздумья о том, как можно поменять модель в будущем
10 пpимет, которые всегда сбываются
Maks 31.03.2026
1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .
Перемещение выделенных строк ТЧ из одного документа в другой
Maks 31.03.2026
Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave
DevAlt 30.03.2026
Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru