Рубрики

Проверьте, является ли число Flavius Number

CS - Placements, Математика

Дана серия целых чисел от 1 до бесконечности и число N.

Задача состоит в том, чтобы удалить каждый (i + 1) -й элемент из оставшегося ряда на каждой i-й итерации и обнаружить, что данное число N существует в ряду или нет.

Номер Флавиуса :

Numbers in the Flavius Sieve are called Flavius Numbers.

Flavius sieve starts with the natural numbers and keep repeating the below step:
At the k-th sieving step, remove every (k+1)-st term of the sequence remaining of N natural numbers after the (k-1)-st sieving step.

For Example: 1, 3, 7, 13, 19, 27, 39, 49,

Примеры:

Input: N = 17
Output: N0

Series after i-th iterations
1). 1, 3, 5, 7, 9, 11, 13, 15, 17, …
2). 1, 3, 7, 9, 13, 15, 19, 21, 25, …
3). 1, 3, 7, 13, 15, 19, 25, …
4). 1, 3, 7, 13, 19, 27, ….

Input: N = 3
Output: Yes

Подходить:

  • Если данное число даже так, ответом будет просто «Нет». Потому что на первой итерации все четные числа были исключены из ряда.
  • Повторите этот процесс.
    • В противном случае удалите количество элементов, удаленных на 1-й итерации, т.е. (1/2)-го числа, а затем проверьте
      если он делится на 3, ответ должен быть «Нет», иначе вычтите числа перед ним, которые были
      убрал т. е. (1/3) число и т. д.
    • Повторите шаг выше для всех итераций, пока мы не получим ответ.

Ниже приведена реализация подхода:

C ++

// реализация C ++
#include <bits/stdc++.h>

using namespace std;

  
// Возвращаем число
// Плавное число или нет

bool Survives(int n)

{

    int i;

  

    // индекс я начинаю с 2, потому что

    // на 1-й итерации каждую 2-ю

    // элемент был удален и сохранен

    // собираемся на k-ю итерацию

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

        if (i > n)

            return true;

        if (n % i == 0)

            return false;

  

        // удаляем элементы которые

        // уже удалены на k-й итерации

        n -= n / i;

    }

}

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

int main()

{

    int n = 17;

    if (Survives(n))

        cout << "Yes" << endl;

    else

        cout << "No" << endl;

  

    return 0;

}

Джава

// Java реализация вышеуказанного подхода

class GFG 

{

  
// Возвращаем число
// Плавное число или нет

static boolean Survives(int n)

{

  

    // индекс я начинаю с 2, потому что

    // на 1-й итерации каждую 2-ю

    // элемент был удален и сохранен

    // собираемся на k-ю итерацию

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

    {

        if (i > n)

            return true;

        if (n % i == 0)

            return false;

  

        // удаляем элементы которые

        // уже удалены на k-й итерации

        n -= n / i;

    }

}

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

public static void main(String[] args)

{

    int n = 17;

    if (Survives(n))

        System.out.println("Yes");

    else

        System.out.println("No");

}
} 

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

python3

# Python3 реализация
# вышеуказанный подход

  
# Вернуть номер
# Плавный номер или нет

def Survives(n) :

  

    # index я начинаю с 2, потому что

    # на 1-й итерации каждую 2-ю

    # элемент был удален и сохранен

    # собирается на k-ю итерацию

    i = 2

    while(True) :

          

        if (i > n) :

            return True; 

              

        if (n % i == 0) :

            return False; 

  

        # удаление элементов, которые

        # уже удалено на k-й итерации

        n -= n // i;

        i += 1

  
Код водителя

if __name__ == "__main__" : 

  

    n = 17; 

      

    if (Survives(n)) :

        print("Yes");

          

    else :

        print("No");

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

C #

// C # реализация вышеуказанного подхода

using System;

  

class GFG 

{

  
// Возвращаем число
// Плавное число или нет

static bool Survives(int n)

{

  

    // индекс я начинаю с 2, потому что

    // на 1-й итерации каждую 2-ю

    // элемент был удален и сохранен

    // собираемся на k-ю итерацию

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

    {

        if (i > n)

            return true;

        if (n % i == 0)

            return false;

  

        // удаляем элементы которые

        // уже удалены на k-й итерации

        n -= n / i;

    }

}

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

public static void Main(String[] args)

{

    int n = 17;

    if (Survives(n))

        Console.WriteLine("Yes");

    else

        Console.WriteLine("No");

}
} 

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

Выход:

No

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

Проверьте, является ли число Flavius Number

0.00 (0%) 0 votes