Как найти числа с пятью делителями

Improve Article

Save Article

Like Article

  • Read
  • Discuss

    • Improve Article

    Save Article

    Like Article

    Given a positive integer N, the task is to count the number of integers from the range [1, N] having exactly 5 divisors.

    Examples:

    Input: N = 18
    Output: 1
    Explanation:
    From all the integers over the range [1, 18], 16 is the only integer that has exactly 5 divisors, i.e. 1, 2, 8, 4 and 16.
    Therefore, the count of such integers is 1.

    Input: N = 100
    Output: 2

    Naive Approach: The simplest approach to solve the given problem is to iterate over the range [1, N] and count those integers in this range having the count of divisors as 5. 

    C++

    #include <iostream>

    #include <cmath>

    using namespace std;

    void SieveOfEratosthenes(int n, bool prime[],

                             bool primesquare[], int a[]) {

        for (int i = 2; i <= n; i++)

            prime[i] = true;

        for (int i = 0; i <= (n * n + 1); i++)

            primesquare[i] = false;

        prime[1] = false;

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

            if (prime[p] == true) {

                for (int i = p * p; i <= n; i += p)

                    prime[i] = false;

            }

        }

        int j = 0;

        for (int p = 2; p <= n; p++) {

            if (prime[p]) {

                a[j] = p;

                primesquare[p * p] = true;

                j++;

            }

        }

    }

    int countDivisors(int n) {

        if (n == 1)

            return 1;

        bool prime[n + 1], primesquare[n * n + 1];

        int a[n];

        SieveOfEratosthenes(n, prime, primesquare, a);

        int ans = 1;

        for (int i = 0;; i++) {

            if (a[i] * a[i] * a[i] > n)

                break;

            int cnt = 1;

            while (n % a[i] == 0)

            {

                n = n / a[i];

                cnt = cnt + 1;

            }

            ans = ans * cnt;

        }

        if (prime[n])

            ans = ans * 2;

        else if (primesquare[n])

            ans = ans * 3;

        else if (n != 1)

            ans = ans * 4;

        return ans;

    }

    int countIntegers(int n) {

          int count = 0;

          for (int i = 1; i <= n; i++) {

            int divisors = countDivisors(i);

            if (divisors == 5 ) {

                count++;

            }

        }

        return count;

    }

    int main() {

        int n = 100;

        cout << countIntegers(n) << endl;

        return 0;

    }

    Java

    import java.util.Vector;

    public class GFG {

        static void SieveOfEratosthenes(int n, boolean prime[],

                                        boolean primesquare[],

                                        int a[])

        {

            for (int i = 2; i <= n; i++)

                prime[i] = true;

            for (int i = 0; i < ((n * n) + 1); i++)

                primesquare[i] = false;

            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;

                }

            }

            int j = 0;

            for (int p = 2; p <= n; p++) {

                if (prime[p]) {

                    a[j] = p;

                    primesquare[p * p] = true;

                    j++;

                }

            }

        }

        static int countDivisors(int n)

        {

            if (n == 1)

                return 1;

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

            boolean primesquare[] = new boolean[(n * n) + 1];

            int a[] = new int[n];

            SieveOfEratosthenes(n, prime, primesquare, a);

            int ans = 1;

            for (int i = 0;; i++) {

                if (a[i] * a[i] * a[i] > n)

                    break;

                int cnt = 1;

                while (n % a[i] == 0) {

                    n = n / a[i];

                    cnt = cnt + 1;

                }

                ans = ans * cnt;

            }

            if (prime[n])

                ans = ans * 2;

            else if (primesquare[n])

                ans = ans * 3;

            else if (n != 1)

                ans = ans * 4;

            return ans;

        }

        static int countIntegers(int n)

        {

            int count = 0;

            for (int i = 1; i <= n; i++) {

                int divisors = countDivisors(i);

                if (divisors == 5) {

                    count++;

                }

            }

            return count;

        }

        public static void main(String[] args)

        {

            int N = 100;

            System.out.println(countIntegers(N));

        }

    }

    Python3

    import math

    def sieveOfEratosthenes(n):

        prime = [True for i in range(n+1)]

        p = 2

        while(p * p <= n):

            if (prime[p] == True):

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

                    prime[i] = False

            p += 1

        primes = []

        for p in range(2, n+1):

            if prime[p]:

                primes.append(p)

        return primes

    def countDivisors(n, primes):

        if (n == 1):

            return 1

        ans = 1

        i = 0

        while (primes[i] <= math.sqrt(n)):

            cnt = 1

            while (n % primes[i] == 0):

                n = n // primes[i]

                cnt += 1

            ans = ans * cnt

            i += 1

        if (n > 1):

            ans = ans * 2

        return ans

    def countIntegers(n):

        count = 0

        primes = sieveOfEratosthenes(n)

        for i in range(1, n+1):

            divisors = countDivisors(i, primes)

            if (divisors == 5 and int(math.sqrt(i))**2 == i):

                count += 1

        return count

    if __name__ == "__main__":

      n = 100

      print(countIntegers(n))

    Javascript

    function sieveOfEratosthenes(n)

    {

      let prime = new Array(n+1).fill(true);

      let p = 2;

      while(p * p <= n)

      {

        if (prime[p] == true)

        {

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

            prime[i] = false;

          }

        }

        p += 1;

      }

      let primes = [];

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

        if (prime[p] == true) {

          primes.push(p);

        }

      }

      return primes;

    }

    function countDivisors(n, primes)

    {

      if (n == 1) {

        return 1;

      }

      let ans = 1;

      let i = 0;

      while (primes[i] <= Math.sqrt(n))

      {

        let cnt = 1;

        while (n % primes[i] == 0) {

          n = n / primes[i];

          cnt += 1;

        }

        ans = ans * cnt;

        i += 1;

      }

      if (n > 1) {

        ans = ans * 2;

      }

      return ans;

    }

    function countIntegers(n) {

      let count = 0;

      let primes = sieveOfEratosthenes(n);

      for (let i = 1; i <= n; i++)

      {

        let divisors = countDivisors(i, primes);

        if (divisors == 5 && Math.sqrt(i)**2 == i) {

          count += 1;

        }

      }

      return count;

    }

    let n = 100;

    console.log(countIntegers(n));

    Time Complexity: O(N4/3)
    Auxiliary Space: O(1)

    Efficient Approach: The above approach can also be optimized by observing a fact that the numbers that have exactly 5 divisors can be expressed in the form of p4, where p is a prime number as the count of divisors is exactly 5. Follow the below steps to solve the problem:

    • Generate all primes such that their fourth power is less than 1018  by using Sieve of Eratosthenes and store it in vector, say A[].
    • Initialize two variables, say low as 0 and high as A.size() – 1.
    • For performing the Binary Search iterate until low is less than high and perform the following steps:
      • Find the value of mid as the (low + high)/2.
      • Find the value of fourth power of element at indices mid (mid – 1) and store it in a variable, say current and previous respectively.
      • If the value of current is N, then print the value of A[mid] as the result.
      • If the value of current is greater than N and previous is at most N, then print the value of A[mid] as the result.
      • If the value of current is greater than N then update the value of high as (mid – 1). Otherwise, update the value of low as (mid + 1).

    Below is the implementation of the above approach:

    C++

    #include <bits/stdc++.h>

    #define ll long long int

    const int MAX = 1e5;

    using namespace std;

    ll power(ll x, unsigned ll y)

    {

        ll res = 1;

        if (x == 0)

            return 0;

        while (y > 0) {

            if (y & 1)

                res = (res * x);

            y = y >> 1;

            x = (x * x);

        }

        return res;

    }

    void SieveOfEratosthenes(

        vector<pair<ll, ll> >& v)

    {

        bool prime[MAX + 1];

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

        prime[1] = false;

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

            if (prime[p] == true) {

                for (int i = p * 2;

                     i <= MAX; i += p)

                    prime[i] = false;

            }

        }

        int num = 1;

        for (int i = 1; i <= MAX; i++) {

            if (prime[i]) {

                v.push_back({ i, num });

                num++;

            }

        }

    }

    int countIntegers(ll n)

    {

        if (n < 16) {

            return 0;

        }

        vector<pair<ll, ll> > v;

        SieveOfEratosthenes(v);

        int low = 0;

        int high = v.size() - 1;

        while (low <= high) {

            int mid = (low + high) / 2;

            ll curr = power(v[mid].first, 4);

            ll prev = power(v[mid - 1].first, 4);

            if (curr == n) {

                return v[mid].second;

            }

            else if (curr > n and prev <= n) {

                return v[mid - 1].second;

            }

            else if (curr > n) {

                high = mid - 1;

            }

            else {

                low = mid + 1;

            }

        }

        return 0;

    }

    int main()

    {

        ll N = 100;

        cout << countIntegers(N);

        return 0;

    }

    Java

    import java.util.Vector;

    public class GFG {

        static int MAX = (int)1e5;

        public static class pair {

            long first;

            long second;

            pair(long first, long second)

            {

                this.first = first;

                this.second = second;

            }

        }

        static long power(long x, long y)

        {

            long res = 1;

            if (x == 0)

                return 0;

            while (y > 0)

            {

                if ((y & 1) == 1)

                    res = (res * x);

                y = y >> 1;

                x = (x * x);

            }

            return res;

        }

        static void SieveOfEratosthenes(Vector<pair> v)

        {

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

            for (int i = 0; i < prime.length; i++) {

                prime[i] = true;

            }

            prime[1] = false;

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

                if (prime[p] == true) {

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

                        prime[i] = false;

                }

            }

            int num = 1;

            for (int i = 1; i <= MAX; i++) {

                if (prime[i]) {

                    v.add(new pair(i, num));

                    num++;

                }

            }

        }

        static long countIntegers(long n)

        {

            if (n < 16) {

                return 0;

            }

            Vector<pair> v = new Vector<>();

            SieveOfEratosthenes(v);

            int low = 0;

            int high = v.size() - 1;

            while (low <= high) {

                int mid = (low + high) / 2;

                long curr = power(v.get(mid).first, 4);

                long prev = power(v.get(mid - 1).first, 4);

                if (curr == n) {

                    return v.get(mid).second;

                }

                else if (curr > n && prev <= n) {

                    return v.get(mid - 1).second;

                }

                else if (curr > n) {

                    high = mid - 1;

                }

                else {

                    low = mid + 1;

                }

            }

            return 0;

        }

        public static void main(String[] args)

        {

            long N = 100;

            System.out.println(countIntegers(N));

        }

    }

    Python3

    def power(x, y):

        res = 1

        if x == 0:

            return 0

        while y > 0:

            if y&1:

                res = (res*x)

            y = y >> 1

            x = (x*x)

        return res

    def sieveofeartoshenes(vec):

        prime = []

        for i in range(pow(10, 5)+1):

            prime.append(True)

        prime[1] = False

        p = 2

        while (p * p <= pow(10, 5)):

            if (prime[p] == True):

                for i in range(p * p, pow(10, 5) + 1, p):

                    prime[i] = False

            p += 1

        num = 1

        for i in range(1, pow(10, 5)+1):

            if prime[i]:

                vec.append([i, num])

                num += 1

    def count_integer(n):

        if n < 16:

            return 0

        vec = [[]]

        sieveofeartoshenes(vec)

        low = 0

        high = len(vec)-1

        while low <= high:

            mid = (low+high)//2

            curr = power(vec[mid][0], 4)

            prev = power(vec[mid-1][0], 4)

            if curr == n:

                return vec[mid][1]

            elif curr > n and prev <= n:

                return vec[mid-1][1]

            elif curr > n:

                high = mid - 1

            else:

                low = mid + 1

    n = 100

    ans = count_integer(n)

    print(ans)

    C#

    using System;

    using System.Collections.Generic;

    public class pair {

        public long first;

        public long second;

        public pair(long first, long second)

        {

            this.first = first;

            this.second = second;

        }

    }

    class GFG {

        static int MAX = (int)1e5;

        static long power(long x, long y)

        {

            long res = 1;

            if (x == 0)

                return 0;

            while (y > 0) {

                if ((y & 1) == 1)

                    res = (res * x);

                y = y >> 1;

                x = (x * x);

            }

            return res;

        }

        static void SieveOfEratosthenes(List<pair> v)

        {

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

            for (int i = 0; i < prime.Length; i++) {

                prime[i] = true;

            }

            prime[1] = false;

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

                if (prime[p] == true) {

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

                        prime[i] = false;

                }

            }

            int num = 1;

            for (int i = 1; i <= MAX; i++) {

                if (prime[i]) {

                    v.Add(new pair(i, num));

                    num++;

                }

            }

        }

        static long countIntegers(long n)

        {

            if (n < 16) {

                return 0;

            }

            List<pair> v = new List<pair>();

            SieveOfEratosthenes(v);

            int low = 0;

            int high = v.Count - 1;

            while (low <= high) {

                int mid = (low + high) / 2;

                long curr = power(v[mid].first, 4);

                long prev = power(v[mid - 1].first, 4);

                if (curr == n) {

                    return v[mid].second;

                }

                else if (curr > n && prev <= n) {

                    return v[mid - 1].second;

                }

                else if (curr > n) {

                    high = mid - 1;

                }

                else {

                    low = mid + 1;

                }

            }

            return 0;

        }

        public static void Main(string[] args)

        {

            long N = 100;

            Console.WriteLine(countIntegers(N));

        }

    }

    Javascript

    function power(x, y)

    {

        let res = 1;

        if (x === 0) {

            return 0;

        }

        while (y > 0)

        {

            if (y&1) {

                res = (res*x);

            }

            y = y >> 1;

            x = (x*x);

        }

        return res;

    }

    function sieveofeartoshenes(vec) {

        let prime = [];

        for (let i = 0; i <= Math.pow(10, 5)+1; i++) {

            prime.push(true);

        }

        prime[1] = false;

        let p = 2;

        while (p * p <= Math.pow(10, 5)) {

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

                for (let i = p * p; i <= Math.pow(10, 5) + 1; i += p) {

                    prime[i] = false;

                }

            }

            p += 1;

        }

        let num = 1;

        for (let i = 1; i <= Math.pow(10, 5)+1; i++)

        {

            if (prime[i]) {

                vec.push([i, num]);

                num += 1;

            }

        }

    }

    function count_integer(n)

    {

        if (n < 16) {

            return 0;

        }

        let vec = [[]];

        sieveofeartoshenes(vec);

        let low = 0;

        let high = vec.length-1;

        while (low <= high)

        {

            let mid = (low+high)

            let curr = power(vec[mid][0], 4);

            let prev = power(vec[mid-1][0], 4);

            if (curr === n)

            {

                return vec[mid][1];

            }

            else if (curr > n && prev <= n)

            {

                return vec[mid-1][1];

            }

            else if (curr > n)

            {

                high = mid - 1;

            }

            else

            {

                low = mid + 1

            }

        }

    }

    let n = 100

    let ans = count_integer(n)

    console.log(ans)

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

    Last Updated :
    13 Apr, 2023

    Like Article

    Save Article

    Источник

    Найти все делители числа

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

    Найдем делители следующих чисел:
    делители числа 2 = 1, 2;
    делители числа 5 = 1, 5 ;
    делители числа 12 = 1, 2, 3, 4, 6, 12 ;
    делители числа 18 = 1, 2, 3, 6, 9, 18 ;
    делители числа 24 = 1, 2, 3, 4, 6, 8, 12, 24 ;
    делители числа 36 = 1, 2, 3, 4, 6, 9, 12, 18, 36

    ×

    Пожалуйста напишите с чем связна такая низкая оценка:

    ×

    Для установки калькулятора на iPhone — просто добавьте страницу
    «На главный экран»

    Для установки калькулятора на Android — просто добавьте страницу
    «На главный экран»

    Смотрите также

    Источник

    Это не ответ на ваш вопрос, а другой подход к решению задачи. Можно проверять числа, разлагая их на делители, а можно конструировать подходящие числа из делителей.

    Разложим искомое число на простые. Так как в дальнейшем нас будут интересовать нечётные делители, степень двойки выписана отдельно:

    n = 2k0 p1k1 p2k2 … piki,

    где k0 — целое неотрицательное, k1, k2, …, ki — натуральные, p1, p2, …, pi — различные нечётные простые.

    Любой делитель n конструируется как произведение простых из разложения выше. Сколько нечётных делителей мы можем сконструировать? (k1 + 1)(k2 + 1) … (ki + 1). Это произведение может быть равно пяти только если у числа ровно один нечётный простой делитель, который возводится в четвёртую степень.

    Подробности можно посмотреть тут: функция делителей.

    Искомое число должно иметь вид 2k p4, где k — целое неотрицательное, p — нечётное простое. Сами нечётные делители тогда имеют вид 1, p, p2, p3, p4.

    Будем искать такие числа в нужном диапазоне. Функция is_prime написана как можно проще, оценка показывает, что проверять числа больше 80 не нужно:

    def is_prime(n):
    return all(n % i != 0 for i in range(2, n))


def numbers(m, n):
    i = 3
    while True:
        if is_prime(i):
            j = i ** 4
            if n < j:
                break
            while j <= n:
                if m <= j:
                    yield j
                j *= 2
        i += 2


print(*sorted(numbers(35_000_000, 40_000_000)), sep='n')

    $ time python five_odd_divisors.py 
35819648
38950081
39037448
39337984

real  0m0.021s
user  0m0.020s
sys   0m0.000s
    Источник

    Нахождение всех делителей числа

    • Все делители числа
    • Калькулятор нахождения всех делителей

    Все делители числа

    Все делители, на которые данное число делится нацело, можно получить из разложения числа на простые множители.

    Нахождение всех делителей числа выполняется следующим образом:

    1. Сначала нужно разложить данное число на простые множители.
    2. Выписываем каждый полученный простой множитель (без повторов, если какой-то множитель повторяется).
    3. Далее, находим всевозможные произведения всех полученных простых множителей между собой и добавляем их к выписанным простым множителям.
    4. В конце добавляем в качестве делителя единицу.

    Например, найдём все делители числа  40.  Раскладываем число  40  на простые множители:

    40 = 23 · 5.

    Выписываем (без повторов) каждый полученный простой множитель — это  2  и  5.

    Далее находим всевозможные произведения всех полученных простых множителей между собой:

    2 · 2 = 4,
    2 · 2 · 2 = 8,
    2 · 5 = 10,
    2 · 2 · 5 = 20,
    2 · 2 · 2 · 5 = 40.

    Добавляем в качестве делителя  1.  В итоге получаем все делители, на которые число  40  делится без остатка:

    1,  2,  4,  5,  8,  10,  20,  40.

    Других делителей у числа  40  нет.

    Калькулятор нахождения всех делителей

    Данный калькулятор поможет вам получить все делители числа. Просто введите число и нажмите кнопку «Вычислить».

    Источник

    Задача. а) Приведите пример трёхзначного числа, у которого ровно 5 натуральных делителей.

    б) Существует ли такое трёхзначное число, у которого ровно 15 натуральных делителей?

    в) Сколько существует таких трёхзначных чисел, у которых ровно 20 натуральных делителей?

    Решение.

    Мы умеем записывать каноническое разложение числа на простые множители. Например, 24 = 23 ∙ 3 – каноническое разложение числа 24 на простые множители. Существует правило:

    если число можно представить в виде

    где m1, m2, … , mk – натуральные показатели, то количество делителей числа n будет равно (m1+1) ∙ (m2+1) ∙ ∙∙∙ ∙ (mk+1).

    Так, например, у числа 24 = 23 ∙ 31 всего (3+1)(1+1) = 4 ∙ 2 = 8 делителей.

    Проверьте: 24 делится на 1; 2; 3; 4; 6; 8; 12 и на 24.

    а) Трёхзначное число, у которого 5 делителей, в каноническом виде есть произведение степеней с такими натуральными делителями m1, m2, … , mk,

    чтобы (m1+1) ∙ (m2+1) ∙ ∙∙∙ ∙ (mk+1) = 5. Так как 5 = 1 ∙ 5, то показатели степеней должны быть 0 и 4.

    Подойдёт а=5. Получаем 1 ∙ 54 = 625. Это число имеет 5 делителей: 1; 5; 25; 125; 625.

    б) 15 = 3 ∙ 5. Следовательно, будем искать число, каноническое разложение которого равно

    Возьмём а1 = 3; а2 = 2 для примера.

    Получим 32 ∙ 24 = 9 ∙ 16 = 144 – трёхзначное число.

    У числа 144 ровно 15 делителей: 1; 2; 3; 4; 6; 8; 9; 12; 16; 18; 24; 36; 48; 72; 144.

    Если возьмём а1 = 2; а2 = 3, то получим 22 ∙ 34 = 4 ∙ 81 = 324 – тоже трёхзначное число, и у него тоже ровно 15 делителей:

    1; 2; 3; 4; 6; 9; 12; 18; 27; 36; 54; 81; 108; 162; 324.

    в) 20 = 4 ∙ 5, значит, возможно произведение  двух степеней с натуральными основаниями, показатели которых 3 и 4.

    Например, 23 ∙ 34 = 648 (подходит, это 1-ое трёхзначное число),

    24 ∙ 33 = 432 (2-ое число), 24 ∙ 53 = 2000 (это четырёхзначное число, не подойдёт).

    20 = 2 ∙ 2 ∙ 5. Это означает, что каноническое разложение может представлять собой произведение трёх степеней с простыми натуральными основаниями и показателями 1, 1 и 4.

    Подберём простые натуральные числа в качестве оснований степеней а1, а2 и а3 так, чтобы в результате получались трёхзначные числа.

    24 ∙ 3 ∙ 5 = 240 (3-е число),

    24 ∙ 3 ∙ 7 = 336 (4-ое число),

    24 ∙ 3 ∙ 11 = 528 (5-ое число),

    24 ∙ 3 ∙ 13 = 624 (6-ое число),

    24 ∙ 3 ∙ 17 = 816 (7-ое число),

    24 ∙ 3 ∙ 19 = 912 (8-ое число),

    24 ∙ 5 ∙ 7 = 560 (9-ое число),

    24 ∙ 5 ∙ 11 = 880 (10-ое число),

    34 ∙ 2 ∙ 5 = 810 (11-ое число),

    34 ∙ 2 ∙ 7 = 1134 (не подойдёт).

    Ответ: а) 625; б) да, 144; в) 11.

    Источник

    Понравилась статья? Поделить с друзьями:
  • Как найти спутники на garmin
  • Как найти коэффициент поступления
  • Обезвреживание бомбы как найти
  • Как найти площять круга
  • Как найти дом путина