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

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

Войти
Регистрация
Восстановить пароль
 
fs444
7 / 11 / 0
Регистрация: 18.08.2009
Сообщений: 484
#1

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

17.03.2010, 21:27. Просмотров 670. Ответов 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
Миниатюры
Граница проверки простого числа  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.03.2010, 21:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Граница проверки простого числа (C++):

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

Определение простого числа - C++
С клавиатуры вводят натуральное 3-х значное число. Является ли оно простым (простые числа делятся нацело только на 1 и на себя). Описать...

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

Генерация простого числа - C++
Необходима программа которая бы генерировала какое-то любое простое число от 2 до N . N пусть ограничивается самым длинным типом данных.

поиск простого числа - C++
Не могу понять почему если вводить 2 или 3, то он их не считает за простые числа. а любое другое простое число выводится, но оно то...

Поиск простого числа - C++
не могу понять почему числа дублируются #include &lt;iostream&gt; using namespace std; int main() { int a, b, c, i, j; c...

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

Максимальное число до которого нужно проверять - это sqrt(10000) = 100
0
fs444
7 / 11 / 0
Регистрация: 18.08.2009
Сообщений: 484
22.03.2010, 21:57  [ТС] #3
odip, понятно, спасибо =)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.03.2010, 21:57
Привет! Вот еще темы с ответами:

Поиск простого числа - C++
с целочисленного массива надо вывести первое простое число далее выводить числа пока не дойдет к следующему простому. Помогите пожалуйста...

Генерация случайного простого числа - C++
Добрый вечер всем! У меня такая проблемма. Необходимо чтобы сгенерировалось 2 простых случайных числа. Для этого я написал функцию с...

Поиск простого отрицательного числа - C++
Вот собственно, положительные простые она находит, а отрицательные - нет. for (i = 0; i &lt; x; i++){ for (j = 0; j&lt; x; j++){ ...

Функция для простого числа - C++
В головной функции ввести массив чисел.И вывести количество простых чисел.Вот программа.Только почему-то, если она натыкается на составное...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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