Определение полупростоты числа, введенного с клавиатуры

@Kriegsmarine · Регистрация: 08.10.2020

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

Добрый вечер, уважаемые пользователи форума.
У меня возникли огромные проблемы при написании программы (язык C++), определяющей, является ли число, введенное с клавиатуры, полупростым. После нескольких лет программирования на языке Python мгновенно перестроиться на C++ у меня не вышло (я студент первого курса, в школьную программу не входило изучение C++), поэтому я прошу помощи у знатоков.
Требуется написать программу, которая определяет, является ли число, введенное с клавиатуры, полупростым. Желательно с пояснениями, но это совсем не обязательно. Заранее огромное спасибо!

@OriRaven · 23.09.2021, 23:35

Kriegsmarine,

C++

#include <iostream>
using namespace std;
 
bool checkSemiprime(int number)
{
    int count = 0;
    for(int i = 2; count < 2 && i * i <= number; ++i)
        while(number % i == 0)
            number /= i, ++count;
    if(number > 1)
        ++count;
    return count == 2;
} 
 
int main()
{
    int number; cin >> number;
    if(checkSemiprime(number))
        cout << "Число полупростое\n";
    else
        cout << "Число не полупростое\n";
}

Байт · 24.09.2021, 11:22

OriRaven, делается много лишнего. Выходить из программы нужно сразу, как только count стал больше 2

@OriRaven · 24.09.2021, 13:36

Сообщение от Байт

Выходить из программы нужно сразу, как только count стал больше 2

Согласен с вами, можно добавить в цикл while дополнительное условие выхода, но в целом, если учитывать, что максимальное простое число, которое при возведении в квадрат укладывается в ограничения int'а - 46337 (то есть циклу for потребуется 46337 итераций, чтобы вычислить, что 46337^2 является полупростым числом), то лишние ~30 операций, на которые программа в худшем случае может застрять в цикле while не выглядят сильно критично

@Kriegsmarine 0 / 0 / 0 Регистрация: 08.10.2020 Сообщений: 1
		1
	Определение полупростоты числа, введенного с клавиатуры 23.09.2021, 20:36. Показов 1367. Ответов 3 Метки c++ (Все метки) Добрый вечер, уважаемые пользователи форума. У меня возникли огромные проблемы при написании программы (язык C++), определяющей, является ли число, введенное с клавиатуры, полупростым. После нескольких лет программирования на языке Python мгновенно перестроиться на C++ у меня не вышло (я студент первого курса, в школьную программу не входило изучение C++), поэтому я прошу помощи у знатоков. Требуется написать программу, которая определяет, является ли число, введенное с клавиатуры, полупростым. Желательно с пояснениями, но это совсем не обязательно. Заранее огромное спасибо! 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	24.09.2021, 11:22	3
	OriRaven, делается много лишнего. Выходить из программы нужно сразу, как только count стал больше 2 0

@OriRaven 38 / 24 / 17 Регистрация: 05.05.2021 Сообщений: 48
	24.09.2021, 13:36	4
	Сообщение от Байт Выходить из программы нужно сразу, как только count стал больше 2 Согласен с вами, можно добавить в цикл while дополнительное условие выхода, но в целом, если учитывать, что максимальное простое число, которое при возведении в квадрат укладывается в ограничения int'а - 46337 (то есть циклу for потребуется 46337 итераций, чтобы вычислить, что 46337^2 является полупростым числом), то лишние ~30 операций, на которые программа в худшем случае может застрять в цикле while не выглядят сильно критично 0

Определение полупростоты числа, введенного с клавиатуры

Решение