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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.81
PG94
2 / 2 / 0
Регистрация: 15.01.2012
Сообщений: 181
#1

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

06.07.2012, 17:51. Просмотров 2133. Ответов 1
Метки нет (Все метки)

Почему, если необ. проверить, является ли число простым(напр. ч-ло n),можно просматривать делители не от 2 до n, а от 2 до sqrt(n)?
P.S. интересует именно этот алгоритм, а точнее, почему после корня из числа не может больше быть делителей.
Спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.07.2012, 17:51     Проверка числа на простоту
Посмотрите здесь:

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

Проверка числа на простоту - C++
Помогите написать программу которая проверяет простое число или нет.

Быстрая проверка натурального числа на простоту - C++
Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь...

Проверка числа на простоту (нужны комментарии) - C++
объясните пожалуйста, как в данной функции выполняется проверка числа на простоту. как можно поподробнее bool Prime(int const num)//...

Проверка на простоту числа - исправить ошибки в коде - C++
Написала программу, она запускается но работает неправильно, почему то все вводимые числа она считает простыми. В чем проблема? ...

Робота с динамической памятью, проверка числа на простоту - C++
В динамическую память последовательно занести введенные с клавиатуры целые числа (признак завершения ввода - число ноль). Проверить все...

[Cи] Проверка чисел на простоту - C++
Как в Си написать программу, которая проверяла бы вводимые числа на простоту вероятностными методами. Числа поряка 10^5000---10^20000 за...

Проверка чисел на простоту - C++
сам код #include "stdafx.h" #include "iostream" #include "vector" using namespace std; int f(int n) { vector<char>...

Проверка номера элемента массива на простоту - C++
Дан массив вещественных чисел.Необходимо вывести сумму чисел, порядковые номера которых являются простыми числами. Как можно осуществить...

Проверка чисел на простоту и проверку на наличие общих цифр в записи - C++
Помогите написать программу: Для каждого (n) из некоторого количества натуральных чисел указать простое число К, ближайшее к числу n и...

Ускорить проверку числа на простоту - C++
Задача заключается в том ,что нужно представить какое-либо число в виде произведения простых чисел (например , вводим 30,выводим...

Проверить на простоту числа заданные выражением - C++
Составить алгоритм для проверки утверждения: «Результатами вычислений по формуле x2 + x + 41 при 0 ≤ x ≤ 40 являются простые числа ». Все...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
06.07.2012, 18:00     Проверка числа на простоту #2
PG94, ну если у нас есть какой-то делитель а который больше sqrt(n), значит должно быть число меньше а которое также является делителем, и оно уж точно меньше sqrt(n). Поэтому и не проверяют.
Yandex
Объявления
06.07.2012, 18:00     Проверка числа на простоту
Ответ Создать тему
Опции темы

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