Как найти числа с тремя делителями

Первый поступивший ответ меня просто убил своей «точностью до наоборот». Я никак не ожидал увидеть подобной формулировки. В то время, как мы имеем простое число, которое делится на единицу и на само себя, нам предлагается умножить его ещё на два. Понятное дело, что получится такое число которое будет делиться на те же два множителя и на само себя. Но ведь добавится и четвёртый — та самая двойка. Возьмите самое первое число из предлагаемой таблицы — «6». Какие у него делители? Очевидно, что «1», «2», «3» и «6». И так по всем числам таблицы. У каждого присутствует четыре разных множителя. А сколько их должно быть по заданию? То-то же.

А это завершающий удар по сознанию, когда именно верный вариант предлагается вычеркнуть, чтобы не путался под ногами. На самом же деле именно его надо было оставить, а остальное удалить. Давайте возьмём первое число из той таблички, что была в вопросе — «2». И возведём его в квадрат, получив «4». Сколько множителей у этого числа? На сколько я знаю, их три — «1», «2» и «4». Аналогичная ситуация, например, с числом «41». Путём возведения в квадрат мы получаем значение «1681», у которого в множителях тоже три числа — «1», «41» и само «1681». Подобным образом можно возвести в квадрат все числа из исходной таблицы, а потом проверить — каждое будет соответствовать условиям задачи:

Таким образом именно квадраты простых чисел имеют по три множителя.

Источник

Given a number N, print all numbers in the range from 1 to N having exactly 3 divisors.

Examples:

Input: N = 16
Output: 4 9
Explanation: 4 and 9 have exactly three divisors.

Input: N = 49
Output: 4 9 25 49
Explanation: 4, 9, 25 and 49 have exactly three divisors.

Mathematical approach to find Numbers with exactly 3 divisors:

To solve the problem follow the below idea:

Idea: After having a close look at the examples mentioned above, you have noticed that all the required numbers are perfect squares and that too of only prime numbers.

Proof: Suppose the number is N, and it is a perfect square with square root X such that X is prime.

Now if we find the factors of N, it will always have following combinations:

1*N

X*X

Therefore the required numbers will have only three numbers as their divisors:

1,

that number itself, and

just a single divisor in between 1 and the number.

Algorithm: We can generate all primes within a set using any sieve method efficiently and then we should take all primes i, such that i*i <=N.

Follow the below steps to solve the problem:

Generate the prime numbers from 1 to N using any sieve method efficiently
Print all the prime numbers(X) between 1 to N, such as X² is less than or equal to N

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void numbersWith3Divisors(int N)

{

bool prime[N + 1];

memset(prime, true, sizeof(prime));

prime[0] = prime[1] = 0;

for (int p = 2; p * p <= N; p++) {

if (prime[p] == true) {

for (int i = p * 2; i <= N; i += p)

prime[i] = false;

}

cout << "Numbers with 3 divisors :n";

for (int i = 0; i * i <= N; i++)

if (prime[i])

cout << i * i << " ";

}

int main()

{

int N = 96;

numbersWith3Divisors(N);

return 0;

}

Java

import java.io.*;

import java.util.*;

class GFG {

static void numbersWith3Divisors(int N)

{

boolean[] prime = new boolean[N + 1];

Arrays.fill(prime, true);

prime[0] = prime[1] = false;

for (int p = 2; p * p <= N; p++) {

if (prime[p] == true) {

for (int i = p * 2; i <= N; i += p)

prime[i] = false;

}

System.out.println("Numbers with 3 divisors : ");

for (int i = 0; i * i <= N; i++)

if (prime[i])

System.out.print(i * i + " ");

}

public static void main(String[] args)

{

int N = 96;

numbersWith3Divisors(N);

}

Python3

def numbersWith3Divisors(N):

prime = [True]*(N+1)

prime[0] = prime[1] = False

p = 2

while (p*p <= N):

if (prime[p] == True):

for i in range(p*2, N+1, p):

prime[i] = False

p += 1

print("Numbers with 3 divisors :")

i = 0

while (i*i <= N):

if (prime[i]):

print(i*i, end=" ")

i += 1

if __name__ == "__main__":

N = 96

numbersWith3Divisors(N)

C#

class GFG {

static void numbersWith3Divisors(int N)

{

bool[] prime = new bool[N + 1];

prime[0] = prime[1] = true;

for (int p = 2; p * p <= N; p++) {

if (prime[p] == false) {

for (int i = p * 2; i <= N; i += p)

prime[i] = true;

}

System.Console.WriteLine(

"Numbers with 3 divisors : ");

for (int i = 0; i * i <= N; i++)

if (!prime[i])

System.Console.Write(i * i + " ");

}

public static void Main()

{

int N = 96;

numbersWith3Divisors(N);

}

PHP

<?php

function numbersWith3Divisors($N)

{

$prime = array_fill(0, $N + 1, true);

$prime[0] = $prime[1] = false;

for ($p = 2; $p * $p <= $N; $p++)

{

if ($prime[$p] == true)

{

for ($i = $p * 2; $i <= $N; $i += $p)

$prime[$i] = false;

}

echo "Numbers with 3 divisors :n";

for ($i = 0; $i * $i <= $N ; $i++)

if ($prime[$i])

echo $i * $i . " ";

}

$N = 96;

numbersWith3Divisors($N);

?>

Javascript

function numbersWith3Divisors(n)

{

let prime = new Array(n+1);

prime.fill(true);

prime[0] = prime[1] = 0;

for (let p = 2; p*p <= n; p++)

{

if (prime[p] == true)

{

for (let i = p*2; i <= n; i += p)

prime[i] = false;

}

document.write("Numbers with 3 divisors :" + "</br>");

for (let i = 0; i*i <= n ; i++)

if (prime[i])

document.write(i*i + " ");

}

let n = 96;

numbersWith3Divisors(n);

Output

Numbers with 3 divisors :
4 9 25 49

Time Complexity: O(N*log(log(N)))
Auxiliary Space: O(N)

Numbers with exactly 3 divisors using constant space:

Run a loop from 2 to sqrt(N) and check if the current element is prime or not, if it is so then print that number, but this method will increase the time complexity of the solution

Follow the below steps to solve the problem:

Start a loop for integer i from 2 to N.
Check if i is prime or not, which can be done easily using the isPrime(n) method.
If i is prime, check if its square is less than or equal to the given number. This will be reviewed only for squares of prime numbers, therefore reducing the number of checks.
If the above condition is satisfied, the number will be printed and the loop will continue till i <= n.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void numbersWith3Divisors(int);

bool isPrime(int);

void numbersWith3Divisors(int N)

{

cout << "Numbers with 3 divisors : " << endl;

for (int i = 2; i * i <= N; i++) {

if (isPrime(i)) {

if (i * i <= N) {

cout << i * i << " ";

}

bool isPrime(int N)

{

for (int i = 2; i * i <= N; i++) {

if (N % i == 0)

return false;

}

return true;

}

int main()

{

int N = 122;

numbersWith3Divisors(N);

return 0;

}

Java

import java.util.*;

class GFG {

static void numbersWith3Divisors(int N)

{

System.out.println("Numbers with 3 divisors : ");

for (int i = 2; i * i <= N; i++) {

if (isPrime(i)) {

if (i * i <= N) {

System.out.print(i * i + " ");

}

public static boolean isPrime(int N)

{

for (int i = 2; i * i <= N; i++) {

if (N % i == 0)

return false;

}

return true;

}

public static void main(String[] args)

{

int N = 122;

numbersWith3Divisors(N);

}

Python3

def numbersWith3Divisors(N):

print("Numbers with 3 divisors : ")

i = 2

while i * i <= N:

if (isPrime(i)):

if (i * i <= N):

print(i * i, end=" ")

i += 1

def isPrime(N):

i = 2

while i * i <= N:

if N % i == 0:

return False

i += 1

return True

if __name__ == "__main__":

N = 122

numbersWith3Divisors(N)

C#

using System;

class GFG {

static void numbersWith3Divisors(int N)

{

Console.WriteLine("Numbers with 3 divisors : ");

for (int i = 2; i * i <= N; i++) {

if (isPrime(i)) {

if (i * i <= N) {

Console.Write(i * i + " ");

}

public static bool isPrime(int N)

{

for (int i = 2; i * i <= N; i++) {

if (N % i == 0)

return false;

}

return true;

}

static void Main()

{

int N = 122;

numbersWith3Divisors(N);

}

Javascript

function numbersWith3Divisors(n)

{

document.write("Numbers with 3 divisors : ");

for(let i = 2; i * i <= n; i++)

{

if (isPrime(i))

{

if (i * i <= n)

{

document.write(i * i + " ");

}

function isPrime(n)

{

if (n == 0 || n == 1)

return false;

for(let i = 2; i * i <= n; i++)

{

if (n % i == 0)

return false;

}

return true;

}

let n = 122;

numbersWith3Divisors(n);

Output

Numbers with 3 divisors : 
4 9 25 49 121

Time Complexity: O(sqrt N²)
Auxiliary Space: O(1)

This article is contributed by Shivam Pradhan (anuj_charm). If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

Last Updated :
07 Nov, 2022

Like Article

Save Article

Источник

doremifasol

0 / 0 / 0

Регистрация: 21.01.2016

Сообщений: 9

Нахождение числа с тремя делителями

04.02.2016, 21:50. Показов 4751. Ответов 25

Метки нет (Все метки)

Доброго времени суток! Помогите, пожалуйста с задачей. Пользователь вводит значения в две переменных m и n. Нужно вывести все числа в диапазоне от m до n у которых только три делителя (1, число само на себя и ещё один делитель). Код для нахождения простых чисел в диапазоне сотворил:

C++

#include "iostream"
using namespace std;
int main(){
int m;
    int n;
    cin >> m;
    cin >> n;
    bool b = true;
    for (; m < n; m++) {
        b = true;
        for (int a = 2; a < m; a++) {
        
            if (!(m%a)) {
                b=false;
                break;
            }
        }
            if (b == true)
                cout << m<<endl;
        }
        system("pause");
}

а вот как ввести проверку на ещё один, третий делитель, ума не приложу. И ещё прошу ответить на один вопрос: Стоит ли продолжать изучение программирования, если не могу самостоятельно решить такую задачу?
Заранее спасибо за ответы!

Programming Эксперт 94731 / 64177 / 26122 Регистрация: 12.04.2006 Сообщений: 116,782	04.02.2016, 21:50
25

4982 / 3089 / 456

Регистрация: 10.11.2010

Сообщений: 11,165

Записей в блоге: 10

04.02.2016, 21:57

Количество делителей больше трёх — не в счёт?

Сообщение от doremifasol

Стоит ли продолжать изучение программирования, если не могу самостоятельно решить такую задачу?

Если интересно — стоит.

Hikari

Хитрая блондиночка $)

1470 / 985 / 399

Регистрация: 21.12.2015

Сообщений: 3,785

04.02.2016, 22:02

Первое, что пришло в голову:

C++

    for (; m < n; m++) {
        int cnt=1;
        for (int a = 2; a < m && cnt<3; a++) if (!(m%a)) cnt++;
        if (cnt==3) cout << m<<endl;
        }

Сообщение от doremifasol

Стоит ли продолжать

…
Есть у водителей такое замечательное правило: Не уверен — не обгоняй.
Так что решать тебе.

4982 / 3089 / 456

Регистрация: 10.11.2010

Сообщений: 11,165

Записей в блоге: 10

04.02.2016, 22:09

value % i == 0 — у value три делителя.

Добавлено через 3 минуты

Сообщение от Hikari

Есть у водителей такое замечательное правило: Не уверен — не обгоняй.

Я тоже не уверен что стану главой компании Microsoft или Google… И что же мне, забить на программирование?

doremifasol

0 / 0 / 0

Регистрация: 21.01.2016

Сообщений: 9

04.02.2016, 22:19

[ТС]

Числа, у которых больше трёх делителей не в счёт

Добавлено через 3 минуты

Сообщение от Hikari

Первое, что пришло в голову:

C++

    for (; m < n; m++) {
        int cnt=1;
        for (int a = 2; a < m && cnt<3; a++) if (!(m%a)) cnt++;
        if (cnt==3) cout << m<<endl;
        }

…
Есть у водителей такое замечательное правило: Не уверен — не обгоняй.
Так что решать тебе.

Сообщение от Hikari

Первое, что пришло в голову:

я такой же код делал, он просто пересчитывает все m до n

Диссидент

27474 / 17161 / 3784

Регистрация: 24.12.2010

Сообщений: 38,670

05.02.2016, 00:37

Ну, во-первых, имеет смысл смотреть только на квадраты простых чисел. Ибо никакие другие числа не могут иметь ровно три делителя. А если по утверждению ТС, он

Сообщение от doremifasol

Код для нахождения простых чисел в диапазоне сотворил:

то задача становится просто тривиальной.

12 / 12 / 5

Регистрация: 02.12.2014

Сообщений: 35

05.02.2016, 02:22

Всё зависит от отрезка{m,n}. Для отрезка {-10,100} будут подходить только простые числа больше 10. Для отрезка {-100,100} чисел вообще не будет.

Добавлено через 17 минут
Хотя я не прав. Для любого отрицательного отрезка чисел не будет. Тогда решение задачи находится в поиске чисел являющихся квадратом простого числа.

20 / 27 / 1

Регистрация: 14.03.2015

Сообщений: 792

05.02.2016, 03:51

Сообщение от doremifasol

Стоит ли продолжать изучение программирования, если не могу самостоятельно решить такую задачу?

Сложно все, но только до тех пор пока Вы в этом не разберетесь. Когда-то Вы и ходить не умели.

Namat

12 / 12 / 5

Регистрация: 02.12.2014

Сообщений: 35

05.02.2016, 04:03

Как-то так:

C++

#include <iostream>
using std::cin;
using std::cout;
#include <cmath>
 
int main(int argc, char *argv[]){
    int m, n;
    cin >> m >>n;
    if (m < 0) return 0;
    for (int i = m; i < n; ++i) {
        //Единица и ноль не является простым числом.
        if(i == 1 || !i) continue;
        double num = sqrt(i);
        bool flag = true;
        //Отсеиваем дробные корни.
        if (fmod(num,1)) continue;
        //Отсеиваем числа делящиеся на 5.
        if (!fmod(num,5) && num > 5) continue;
        //Определяем является ли число простым.
        for (int j = 2; j < sqrt(num) + 1; ++j)
            if (!fmod(num,j)) {
                flag = false;
                break;
            }
        if (flag) cout << i << ' ';
    }
 
    return 0;
}

Хитрая блондиночка $)

1470 / 985 / 399

Регистрация: 21.12.2015

Сообщений: 3,785

05.02.2016, 09:26

Сообщение от castaway

Я тоже не уверен что стану главой компании Microsoft или Google… И что же мне, забить на программирование?

И причем тут этот укол зонтиком?
Разницу между топ-менеджером и программистом ты, надеюсь, знаешь?
Ладно… Это оффтоп. Не важно…

693 / 303 / 99

Регистрация: 04.07.2014

Сообщений: 842

05.02.2016, 10:31

Сообщение от doremifasol

а вот как ввести проверку на ещё один, третий делитель, ума не приложу.

Так поменяй алгоритм.

1, число само на себя и ещё один делитель

Что это за делитель? Очевидно, что простое число, иначе оно даст дополнительные делители. Т.е. тебя просят вывести из диапазона [m,n] числа, являющиеся квадратами простых чисел! Так же, эта задача явно применима только к положительным числам, а точнее к натуральным числам. Иначе её условие бы усложнилось

Тогда первое не оптимальное решение:

находим все простые числа до
выводим квадраты только те из них, которые удовлетворяют условию

castaway

05.02.2016, 10:35

Не по теме:

Сообщение от Hikari

И причем

При том что у тебя аналогия плохая. Мне кажется это не трудно было понять.

provor

3 / 3 / 3

Регистрация: 04.02.2016

Сообщений: 22

05.02.2016, 11:16

Сообщение было отмечено castaway как решение

Решение

Вообще не понимаю, что вы тут устроили. Квадраты простых чисел искать зачем-то придумали. Держи

C++

#include <iostream>
using namespace std;
int main(){
    int n, m, count;
    cin>>n>>m;
    for(int i=n;i<=m;i++){
        count=2;
        for(int j=2;j<m;j++){
            if(i%j==0 && i!=j)count++;
        }
        if(count==3)cout<<i<<" ";
    }
    return 0;
}

castaway

4982 / 3089 / 456

Регистрация: 10.11.2010

Сообщений: 11,165

Записей в блоге: 10

05.02.2016, 11:39

provor, зачем усложнять внутренний цикл? Число не может делится на большее чем само.

C++

#include <iostream>
 
int main() {
    int n, m;
    std::cin >> n >> m;
    for ( int i = n; i <= m; i++ ) {
        int cnt = 2;
        for ( int j = 2; j < i; j++ ) {
            if ( i % j == 0 && i != j ) cnt++;
        }
        if ( cnt == 3 ) std::cout << i << " ";
    }
    return 0;
}

Диссидент

27474 / 17161 / 3784

Регистрация: 24.12.2010

Сообщений: 38,670

05.02.2016, 12:13

Сообщение от castaway

for ( int j = 2; j < i; j++ ) {
if ( i % j == 0 && i != j )

Не понял смысла проверки i!=j
Кроме того, если cnt стало =4, зачем дальше цикл крутить?

4982 / 3089 / 456

Регистрация: 10.11.2010

Сообщений: 11,165

Записей в блоге: 10

05.02.2016, 12:16

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

Не понял смысла проверки i!=j

А его и нет) Код был скопирован и изменён из сообщения выше.

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

Кроме того, если cnt стало =4, зачем дальше цикл крутить?

Тоже верно.

Диссидент

27474 / 17161 / 3784

Регистрация: 24.12.2010

Сообщений: 38,670

05.02.2016, 12:27

И все-таки наиболее эффективным мне кажется перебор простых чисел в диапазоне sqrt(m) — sqrt(n) и вывод их квадратов. Тем более, что для ТС определение простоты числа не составляет проблемы.

3 / 3 / 3

Регистрация: 04.02.2016

Сообщений: 22

05.02.2016, 12:31

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

Не понял смысла проверки i!=j

Вариант i==j учтен априори. В любом случае мог бы скомпилировать без него, если смысла не видишь.

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

Кроме того, если cnt стало =4, зачем дальше цикл крутить?

На счет этого согласен. Но в данном случае это не принципиально, тут суть была в рабочем алгоритме

4982 / 3089 / 456

Регистрация: 10.11.2010

Сообщений: 11,165

Записей в блоге: 10

05.02.2016, 12:39

Сообщение от provor

Вариант i==j учтен априори. В любом случае мог бы скомпилировать без него, если смысла не видишь.

Вы чего бабушку лохматите? Это был комментарий к моему коду, в котором нет смысла на проверку i != j.

3 / 3 / 3

Регистрация: 04.02.2016

Сообщений: 22

05.02.2016, 12:44

Действительно. Навел смуту. Просто сначала не увидел принципиальных изменений вашего кода по сравнению с моим

IT_Exp

Эксперт

87844 / 49110 / 22898

Регистрация: 17.06.2006

Сообщений: 92,604

05.02.2016, 12:44

Помогаю со студенческими работами здесь

Подсчитать количество чисел, меньших данного числа М и являющихся делителями натурального числа Q
составьте программу подсчета числа натуральных чисел,меньших данного числа М и являющихся…

Из массива A, состоящего не более чем из 25 чисел, записать в массив B числа, являющиеся делителями числа Х
Составить программу, которая из массива A, состоящего не более чем из 25 чисел, записывает в массив…

Дан текстовый файл, содержащий целые числа. Найти сумму элементов, являющихся делителями заданного числа
Дан текстовый файл, содержащий целые числа. Найти сумму элементов, являющихся
делителями…

Определить являются ли числа делителями значения суммы первой и предпоследней цифры заданного целого четырехзначного числа
Даны целые числа m и n . Определить являются ли они делителями значения суммы первой и…

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

Или воспользуйтесь поиском по форуму:

Источник

Задумаемся. Чтобы был хотя бы один простой четный делитель, нужно иметь делитель 2.

Если есть еще хотя бы два простых нечетных делителя p и q — имеем делители 2, 2p, 2q, 2pq — перебор!

Если есть один делитель p, но и p^2 тоже — имеем 2, 2p, 2p^2 — три делителя.

Если просто число имеет вид 2p — то делителей четных два.

Если двойка входит дважды — имеем 2 и 4 как делители, плюс 2p и 4p (если есть еще хоть один делитель p) — перебор.

Итак, числа должны быть вида 2*p^2.

Дальше понятно, как проверять быстро?

def is_prime(n):
    if n%2 == 0: return False
    i = 3
    while(i*i <= n):
        if n%i == 0: return False
        i = i+2
    return True

def lp(n):
    p = int((n//2)**0.5)
    if p%2 == 0: p = p + 1
    return p

def nums(m,n):
    p = lp(m)
    q = lp(n)
    while(p <= q):
        if is_prime(p): 
            print(2*p*p)
        p = p + 2

nums(101000000,102000000)

Результат расчета — тут: https://ideone.com/yqYOZ5

Источник

Загрузить PDF

Число называется делителем (или множителем) другого числа в том случае, если при делении на него получается целый результат без остатка.^[1] Для малого числа (например, 6) определить количество делителей довольно легко: достаточно выписать все возможные произведения двух целых чисел, которые дают заданное число. При работе с большими числами определить количество делителей становится сложнее. Тем не менее, если вы разложите целое число на простые множители, то легко сможете определить число делителей с помощью простой формулы.

1
Запишите заданное целое число вверху страницы. Вам понадобится достаточно места для того, чтобы расположить ниже числа дерево множителей. Для разложения числа на простые множители можно использовать и другие методы, которые вы найдете в статье Как разложить число на множители.
- Например, если вы хотите узнать, сколько делителей, или множителей имеет число 24, запишите вверху страницы.
2

Найдите два числа (помимо 1), при перемножении которых получается заданное число. Таким образом вы найдете два делителя, или множителя данного числа. Проведите от данного числа две ветки вниз и запишите на их концах полученные множители.
3
Поищите простые множители. Простым множителем называется такое число, которое делится без остатка лишь на само себя и на 1.^[2] Например, число 7 является простым множителем, так как оно делится без остатка лишь на 1 и 7. Для удобства обводите найденные простые множители кружком.
- Например, 2 является простым числом, поэтому обведите кружком.
4

Продолжайте раскладывать составные (не простые) числа на множители. Проводите следующие ветки от составных чисел до тех пор, пока все множители не станут простыми. Не забывайте обводить простые числа кружками.
5

Представьте каждый простой множитель в степенной форме. Для этого подсчитайте, сколько раз встречается каждый простой множитель в нарисованном дереве множителей. Это число и будет степенью, в которую необходимо возвести данный простой множитель.^[3]
6
Запишите разложение числа на простые множители. Первоначально заданное число равно произведению простых множителей в соответствующих степенях.
- В нашем примере $24=2^{{3}}times 3^{{1}}$ .
Реклама

1
2

Подставьте в формулу величины степеней. Будьте внимательны и используйте степени при простых множителях, а не сами множители.
3

Сложите величины в скобках. Просто прибавьте 1 к каждой степени.
4

Перемножьте полученные величины. В результате вы определите количество делителей, или множителей данного числа .

Реклама

Советы

Если число представляет собой квадрат целого числа (например, 36 является квадратом числа 6), то оно имеет нечетное количество делителей. Если же число не является квадратом другого целого числа, количество его делителей четно.

Об этой статье

Эту страницу просматривали 120 968 раз.

Была ли эта статья полезной?

Источник

Mathematical approach to find Numbers with exactly 3 divisors:

C++

Java

Python3

C#

PHP

Javascript

Numbers with exactly 3 divisors using constant space:

C++

Java

Python3

C#

Javascript

Нахождение числа с тремя делителями

Решение

Советы

Похожие статьи

Об этой статье

Была ли эта статья полезной?

Не пропустите также: