Составить пограмму вычисления количества простых чисел, которые принадлежат отрезку [m,n].Для проверки, является ли число простым использовать функцию

@Аня 13 · Регистрация: 27.04.2010

Author24 — интернет-сервис помощи студентам

Составить пограмму вычисления количества простых чисел, которые принадлежат отрезку [m,n].Для проверки, является ли число простым использовать функцию prostoe.Функция возвращает 1, если число простое, а 0-В остальных случаях.
int prostoe(int n)

C++

{ int d, r;
d=2; 
do {
r=n%d;
if (r!= 0) d++;
}
while (r!=0); 
if (d==n) return 1; 
else return 0;
}

@neske · 04.05.2010, 19:48

Код.

C++

#include <iostream>
int prostoe (int);
 
int main()
{
    int M,N;
    std::cout << "Input M: ";
    std::cin >> M;
    std::cout << "Input N: ";
    std::cin >> N;
 
    for (int i=M; i<=N; i++)
    if ( prostoe(i) ) std::cout << i << "  ";
    return 0;
}
 
int prostoe (int num)
{
    for (int i=2; i<num; i++)
        if (num%i==0)
            return 0;
 
    return 1;
}

Будет непонятно, объясню.

@yanyk1n · 04.05.2010, 19:50

neske, стоит ограничить верхний диапазон перебора:

C++

int prostoe (int num)
{
    for (int i=2; i<=round(sqrt(num)); i++)
        if (num%i==0)
            return 0;
 
    return 1;
}

@neske · 04.05.2010, 19:51

k1ry4, что за round? Не встречался.

Такой вариант тоже более правильный будет?

C++

1	for (int i=2; i<=num/2; i++)

@Manjak · 04.05.2010, 19:54

Для реализации можно испрользовать bitset, а алгоритм - решето Эратосфена

@yanyk1n · 04.05.2010, 19:57

neske, просто максимально возможный простой множитель, входящий в разложение составного числа, равен корню из этого числа.

@neske · 04.05.2010, 20:00

Да, я уже понял =)

Само слово round, непонятно его назначение.

@yanyk1n · 04.05.2010, 20:03

neske, sqrt возвращает тип double, а round - округление. Не исключаю, что этого не требуется в С++, так как там предусмотрен механизм приведения типов.

@Аня 13 · 04.05.2010, 23:35 **[ТС]**

А объясните что означает std?

@Manjak 270 / 176 / 46 Регистрация: 12.03.2010 Сообщений: 494
	04.05.2010, 19:54	5
	Для реализации можно испрользовать bitset, а алгоритм - решето Эратосфена 0

@yanyk1n 4342 / 1474 / 680 Регистрация: 12.03.2009 Сообщений: 5,310
	04.05.2010, 19:57	6
	neske, просто максимально возможный простой множитель, входящий в разложение составного числа, равен корню из этого числа. 0

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	04.05.2010, 20:00	7
	Да, я уже понял =) Само слово round, непонятно его назначение. 0

@yanyk1n 4342 / 1474 / 680 Регистрация: 12.03.2009 Сообщений: 5,310
	04.05.2010, 20:03	8
	neske, sqrt возвращает тип double, а round - округление. Не исключаю, что этого не требуется в С++, так как там предусмотрен механизм приведения типов. 1

@Аня 13 2 / 2 / 0 Регистрация: 27.04.2010 Сообщений: 44
	04.05.2010, 23:35 [ТС]	9
	А объясните что означает std? 0