Рубрики

N-й квадрат бесплатный номер

Учитывая число n, найдите n-ое число без квадратов. Число не содержит квадратов, если оно не делится на идеальный квадрат, отличный от 1.

Примеры :

Input : n = 2
Output : 2

Input : 5
Output : 6
There is one number (in range from 1 to 6) 
that is divisible by a square. The number
is 4.

Метод 1 (грубая сила):
Идея состоит в том, чтобы итеративно проверять каждое число, делится ли оно на любое идеальное квадратное число, и увеличивать число всякий раз, когда встречается число без квадратов, и возвращать число без n-го квадрата.

Ниже приводится реализация:

C ++

// Программа для поиска номера n-го квадрата
#include<bits/stdc++.h>

using namespace std;

  
// Функция для поиска n-го квадратного свободного числа

int squareFree(int n)

{

    // Для подсчета числа свободных квадратов

    int cnt = 0;

  

    // Цикл свободных квадратов

    for (int i=1;; i++)

    {

        bool isSqFree = true;

        for (int j=2; j*j<=i; j++)

        {

            // Проверка, является ли квадрат числа

            // делится на любое число

            // идеальный квадрат

            if (i % (j*j) == 0)

            {

                isSqFree = false;

                break;

            }

        }

  

        // Если число не содержит квадратов

        if (isSqFree == true)

        {

           cnt++;

  

           // Если cnt становится n, вернуть

           // число

           if (cnt == n)

              return i;

        }

    }

    return 0;

}

  
// Программа для водителя

int main()

{

    int n = 10;

    cout << squareFree(n) << endl;

    return 0;

}

Джава

// Java-программа для поиска n-го квадрата
// бесплатный номер

import java.io.*;

  

class GFG {

      

    // Функция для поиска n-го квадрата

    // число

    public static int squareFree(int n) 

    {

          

        // Для подсчета квадрата

        // бесплатный номер

        int cnt = 0;

      

        // Цикл свободных квадратов

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

              

            boolean isSqFree = true;

              

            for (int j = 2; j * j <= i; j++) 

            {

                  

                // Проверяем ли квадрат

                // числа делится

                // по любому номеру

                // идеальный квадрат

                if (i % (j * j) == 0) {

                    isSqFree = false;

                    break;

                }

            }

          

            // Если число не содержит квадратов

            if (isSqFree == true) {

                cnt++;

          

                // Если cnt становится n,

                // вернуть номер

                if (cnt == n)

                    return i;

            }

        }

    }

      

    // управляемый код

    public static void main(String[] args) {

          

        int n = 10;

          

        System.out.println("" + squareFree(n));

    }

}

  
// Этот код предоставлен sunnysingh

python3

# Python3 Программа для поиска nth
# квадратный свободный номер

  
# Функция для поиска n-го квадрата
# бесплатный номер

def squareFree(n):

      

    # Для поддержания количества

    # квадратный свободный номер

    cnt = 0

  

    # Цикл для свободных квадратов

    i = 1;

    while (True): 

        isSqFree = True;

        j = 2;

        while (j * j <= i): 

              

            # Проверка, является ли квадрат числа

            # делится на любое число, которое

            # идеальный квадрат

            if (i % (j * j) == 0):

                isSqFree = False

                break

            j += 1;

  

        # Если число не содержит квадратов

        if (isSqFree == True):

            cnt += 1

      

            # Если cnt становится n, вернуть число

            if (cnt == n): 

                return i; 

        i += 1

  

    return 0

  
Код водителя

n = 10

print(squareFree(n)); 

  
# Этот код предоставлен mits

C #

// C # Программа для поиска
// номер n квадратный свободный

using System;

  

class GFG {

      

    // Функция для поиска nth

    // квадратное свободное число

    public static int squareFree(int n) 

    {

        // Для ведения подсчета

        // квадратное свободное число

        int cnt = 0;

      

        // Цикл свободных квадратов

        for (int i = 1; ; i++) 

        {

            bool isSqFree = true;

              

            for (int j = 2; j * j <= i; j++) 

            {

                // Проверяем ли квадрат

                // числа делится

                // по любому номеру

                // идеальный квадрат

                if (i % (j * j) == 0) {

                    isSqFree = false;

                    break;

                }

            }

          

            // Если число не содержит квадратов

            if (isSqFree == true) {

                cnt++;

          

                // Если cnt становится n,

                // вернуть номер

                if (cnt == n)

                    return i;

            }

        }

    }

      

    // Код драйвера

    public static void Main() 

    {

        int n = 10;

        Console.Write("" + squareFree(n));

    }

}

  
// Этот код предоставлен нитин митталь

PHP

<?php
// PHP программа для поиска
// номер n квадратный свободный

  
// Функция для поиска nth
// квадратное свободное число

function squareFree($n)

{

      

    // Для ведения подсчета

    // квадратное свободное число

    $cnt = 0;

  

    // Цикл для квадрата

    // свободные номера

    for ($i = 1; ; $i++)

    {

        $isSqFree = true;

        for ($j = 2; $j * $j <= $i; $j++)

        {

              

            // Проверка, является ли квадрат числа

            // делится на любое число

            // идеальный квадрат

            if ($i % ($j * $j) == 0)

            {

                $isSqFree = false;

                break;

            }

        }

  

        // Если число не содержит квадратов

        if ($isSqFree == true)

        {

            $cnt++;

      

            // Если cnt становится n,

            // вернуть номер

            if ($cnt == $n)

                return $i;

        }

    }

    return 0;

}

  
// Код драйвера

$n = 10;

echo(squareFree($n));

  
// Этот код предоставлен Ajit.
?>


Выход:

14

Метод 2 (лучший подход):
Идея состоит в том, чтобы считать свободные квадратные числа, меньшие или равные верхнему пределу «k», и затем применить бинарный поиск, чтобы найти n-е квадратное свободное число. Сначала мы вычисляем количество квадратов (числа с квадратами в качестве коэффициентов) до «k», а затем вычитаем это количество из общего числа, чтобы получить количество свободных квадратов до «k».

Объяснение:

  1. Если любое целое число имеет идеальный квадрат как фактор, то гарантируется, что у него также есть квадрат простого числа как фактор. Таким образом, нам нужно посчитать целые числа, меньшие или равные «k», у которых квадрат простых чисел является фактором.
    Например, найдите число целых чисел, которые имеют 4 или 9 в качестве коэффициента до «k». Это может быть сделано с использованием принципа включения-исключения . Используя принцип включения-исключения , общее число целых чисел составляет [k / 4] + [k / 9] — [k / 36], где [] — наибольшая целочисленная функция.
  2. Рекурсивно применяйте включение и исключение, пока значение наибольшего целого не станет равным нулю. Этот шаг вернет количество чисел с квадратами в качестве факторов.
  3. Примените бинарный поиск, чтобы найти номер n-го квадрата.

Ниже приведена реализация вышеуказанного алгоритма:

C ++

// Программа для поиска номера n-го квадрата
#include<bits/stdc++.h>

using namespace std;

  
// Максимальное простое число для квадрата
// делимость

const int MAX_PRIME = 100000;

  
// Максимальное значение результата. Делаем бинарный поиск из 1
// в MAX_RES

const int MAX_RES = 2000000000l;

  

void SieveOfEratosthenes(vector<long long> &a)

{

    // Создаем логический массив "prime [0..n]" и инициализируем

    // все записи это как правда. Значение в простом [i] будет

    // наконец, ложь, если я не простое число, иначе истина.

    bool prime[MAX_PRIME + 1];

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

  

    for (long long p=2; p*p<=MAX_PRIME; p++)

    {

        // Если простое число [p] не изменилось, то это простое число

        if (prime[p] == true)

        {

            // Обновить все кратные р

            for (long long i=p*2; i<=MAX_PRIME; i += p)

                prime[i] = false;

        }

    }

  

    // Сохраняем все простые числа в []

    for (long long p=2; p<=MAX_PRIME; p++)

        if (prime[p])

            a.push_back(p);

}

  
// Функция для подсчета целых чисел до k, которые имеют
// совершенные квадраты как факторы. я индекс следующего
// простое число, квадрат которого нужно проверить.
// curr - текущее число, чей квадрат должен быть проверен.

long long countSquares(long long i, long long cur,

                       long long k, vector<long long> &a)

{

    // переменная для хранения квадрата простого числа

    long long square = a[i]*a[i];

  

    long long newCur = square*cur;

  

    // Если значение наибольшего целого становится равным нулю

    if (newCur > k)

        return 0;

  

    // Применение принципа включения-исключения

  

    // Подсчет целых чисел с квадратами в качестве фактора

    long long cnt = k/(newCur);

  

    // Включение (повтор для следующего простого числа)

    cnt += countSquares(i+1, cur, k, a);

  

    // Исключение (повтор для следующего простого числа)

    cnt -= countSquares(i+1, newCur, k, a);

  

    // Окончательный счет

    return cnt;

}

  
// Функция для возврата n-го квадратного свободного числа

long long squareFree(long long n)

{

    // Вычисление простых чисел и сохранение их в массиве a []

    vector <long long> a;

    SieveOfEratosthenes(a);

  

    // Применение бинарного поиска

    long long low = 1;

    long long high = MAX_RES;

  

    while (low < high)

    {

        long long mid = low + (high - low)/2;

  

        // 'c' содержит количество свободных квадратов

        // меньше или равно 'mid'

        long long c = mid - countSquares(0, 1, mid, a);

  

        // Если c <n, то ищем правую часть середины

        // еще поиск слева от середины

        if (c < n)

            low = mid+1;

        else

            high = mid;

    }

  

    // номер n квадратный свободный

    return low;

}

  
// Программа для водителя

int main()

{

    int n = 10;

    cout << squareFree(n) << endl;

    return 0;

}

Джава

// Java-программа для поиска свободного числа

import java.util.*;

  

class GFG 

{

  
// Максимальное простое число для квадрата
// делимость

static int MAX_PRIME = 100000;

  
// Максимальное значение результата. Мы делаем
// бинарный поиск от 1 до MAX_RES

static int MAX_RES = 2000000000;

  

static void SieveOfEratosthenes(Vector<Long> a)

{

    // Создаем логический массив "prime [0..n]"

    // и инициализируем все записи как

    // правда. Значение в простом [i] будет

    // наконец, ложь, если я не

    // простое число, иначе верно.

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

    Arrays.fill(prime, true);

  

    for (int p = 2; p * p <= MAX_PRIME; p++)

    {

        // Если простое число [p] не изменилось,

        // тогда это простое число

        if (prime[p] == true)

        {

            // Обновить все кратные р

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

                prime[i] = false;

        }

    }

  

    // Сохраняем все простые числа в []

    for (int p = 2; p <= MAX_PRIME; p++)

        if (prime[p])

            a.add((long)p);

}

  
// Функция для подсчета целых чисел до k, которые имеют
// совершенные квадраты как факторы. я индекс следующего
// простое число, квадрат которого нужно проверить.
// curr - текущее число, чей квадрат должен быть проверен.

static long countSquares(long i, long cur,

                    long k, Vector<Long> a)

{

    // переменная для хранения квадрата простого числа

    long square = a.get((int) i)*a.get((int)(i));

  

    long newCur = square*cur;

  

    // Если значение наибольшего целого становится равным нулю

    if (newCur > k)

        return 0;

  

    // Применение принципа включения-исключения

  

    // Подсчет целых чисел с квадратами в качестве фактора

    long cnt = k/(newCur);

  

    // Включение (повтор для следующего простого числа)

    cnt += countSquares(i + 1, cur, k, a);

  

    // Исключение (повтор для следующего простого числа)

    cnt -= countSquares(i + 1, newCur, k, a);

  

    // Окончательный счет

    return cnt;

}

  
// Функция для возврата n-го квадратного свободного числа

static long squareFree(long n)

{

    // Вычисление простых чисел и сохранение их в массиве a []

    Vector <Long> a = new Vector<>();

    SieveOfEratosthenes(a);

  

    // Применение бинарного поиска

    long low = 1;

    long high = MAX_RES;

  

    while (low < high)

    {

        long mid = low + (high - low)/2;

  

        // 'c' содержит количество свободных квадратов

        // меньше или равно 'mid'

        long c = mid - countSquares(0, 1, mid, a);

  

        // Если c <n, то ищем правую часть середины

        // еще поиск слева от середины

        if (c < n)

            low = mid+1;

        else

            high = mid;

    }

  

    // номер n квадратный свободный

    return low;

}

  
// Код драйвера

public static void main(String[] args) 

{

    int n = 10;

    System.out.println(squareFree(n));

}
}

  
// Этот код предоставлен 29AjayKumar

C #

// C # Программа для поиска номера n-го квадрата

using System;

using System.Collections.Generic;

  

class GFG 

{

  
// Максимальное простое число для рассмотрения
// для квадратичной делимости

static int MAX_PRIME = 100000;

  
// Максимальное значение результата. Мы делаем
// бинарный поиск от 1 до MAX_RES

static int MAX_RES = 2000000000;

  

static void SieveOfEratosthenes(List<long> a)

{

    // Создаем логический массив "prime [0..n]"

    // и инициализируем все записи как

    // правда. Значение в простом [i] будет

    // наконец, ложь, если я не

    // простое число, иначе верно.

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

    for(int i = 0; i < MAX_PRIME + 1; i++)

        prime[i] = true;

  

    for (int p = 2; p * p <= MAX_PRIME; p++)

    {

        // Если простое число [p] не изменилось,

        // тогда это простое число

        if (prime[p] == true)

        {

            // Обновить все кратные р

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

                prime[i] = false;

        }

    }

  

    // Сохраняем все простые числа в []

    for (int p = 2; p <= MAX_PRIME; p++)

        if (prime[p])

            a.Add((long)p);

}

  
// Функция для подсчета целых чисел до k, которые имеют
// совершенные квадраты как факторы. я индекс следующего
// простое число, квадрат которого нужно проверить.
// curr - текущее число, чей квадрат должен быть проверен.

static long countSquares(long i, long cur,

                    long k, List<long> a)

{

    // переменная для хранения квадрата простого числа

    long square = a[(int) i]*a[(int)(i)];

  

    long newCur = square * cur;

  

    // Если значение наибольшего целого становится равным нулю

    if (newCur > k)

        return 0;

  

    // Применение принципа включения-исключения

  

    // Подсчет целых чисел с квадратами в качестве фактора

    long cnt = k/(newCur);

  

    // Включение (повтор для следующего простого числа)

    cnt += countSquares(i + 1, cur, k, a);

  

    // Исключение (повтор для следующего простого числа)

    cnt -= countSquares(i + 1, newCur, k, a);

  

    // Окончательный счет

    return cnt;

}

  
// Функция для возврата n-го квадратного свободного числа

static long squareFree(long n)

{

    // Вычисление простых чисел и сохранение их в массиве a []

    List<long> a = new List<long>();

    SieveOfEratosthenes(a);

  

    // Применение бинарного поиска

    long low = 1;

    long high = MAX_RES;

  

    while (low < high)

    {

        long mid = low + (high - low)/2;

  

        // 'c' содержит количество свободных квадратов

        // меньше или равно 'mid'

        long c = mid - countSquares(0, 1, mid, a);

  

        // Если c <n, то ищем правую часть середины

        // еще поиск слева от середины

        if (c < n)

            low = mid + 1;

        else

            high = mid;

    }

  

    // номер n квадратный свободный

    return low;

}

  
// Код драйвера

public static void Main() 

{

    int n = 10;

    Console.WriteLine(squareFree(n));

}
}

  
/ * Этот код предоставлен PrinciRaj1992 * /

Выход:

14

Эта статья предоставлена Рахул Агравал . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

N-й квадрат бесплатный номер

0.00 (0%) 0 votes