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

31.12.2019Математика, Технический Scripter

Учитывая число 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.
?>

Выход:

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

Объяснение:

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

}

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);

}

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 * /

Выход:

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

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

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

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

0.00 (0%) 0 votes