Рубрики

Номера Кармайкла

Число n называется числом Кармайкла, если оно удовлетворяет следующему модулярному арифметическому условию:

  power(b, n-1) MOD n = 1, 
  for all b ranging from 1 to n such that b and 
  n are relatively prime, i.e, gcd(b, n) = 1 

Если задано положительное целое число n, найдите это число Кармайкла. Эти числа имеют значение в методе Ферма для тестирования простоты .

Примеры :

Input :  n = 8
Output : false
Explanation : 8 is not a Carmichael number because 3 is 
              relatively prime to 8 and (38-1) % 8
              = 2187 % 8 is not 1.
              
Input :  n = 561
Output : true

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

Ниже приведена программа для проверки, является ли данное число Кармайклом или нет.

C ++

// Программа на C ++ для проверки, является ли число
// Кармайкл или нет.
#include <iostream>

using namespace std;

  
// утилита для поиска gcd из двух чисел

int gcd(int a, int b)

{

    if (a < b)

        return gcd(b, a);

    if (a % b == 0)

        return b;

    return gcd(b, a % b);

}

  
// функция полезности, чтобы найти pow (x, y) под
// данный модуль по модулю

int power(int x, int y, int mod)

{

    if (y == 0)

        return 1;

    int temp = power(x, y / 2, mod) % mod;

    temp = (temp * temp) % mod;

    if (y % 2 == 1)

        temp = (temp * x) % mod;

    return temp;

}

  
// Эта функция получает целое число n и
// находит, если это число Кармайкла

bool isCarmichaelNumber(int n)

{

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

        // Если "b" относительно простое число к n

        if (gcd(b, n) == 1)

  

            // И pow (b, n-1)% n не равен 1,

            // вернуть false.

            if (power(b, n - 1, n) != 1)

                return false;

    }

    return true;

}

  
// Функция драйвера

int main()

{

    cout << isCarmichaelNumber(500) << endl;

    cout << isCarmichaelNumber(561) << endl;

    cout << isCarmichaelNumber(1105) << endl;

    return 0;

}

Джава

// JAVA-программа для проверки, является ли число
// Кармайкл или нет.

import java.io.*;

  

class GFG {

  

    // функция полезности для поиска gcd из

    // два числа

    static int gcd(int a, int b)

    {

        if (a < b)

            return gcd(b, a);

        if (a % b == 0)

            return b;

        return gcd(b, a % b);

    }

  

    // функция полезности для поиска pow (x, y)

    // по заданному модулю

    static int power(int x, int y, int mod)

    {

        if (y == 0)

            return 1;

        int temp = power(x, y / 2, mod) % mod;

        temp = (temp * temp) % mod;

        if (y % 2 == 1)

            temp = (temp * x) % mod;

        return temp;

    }

  

    // Эта функция получает целое число n и

    // находит, если это число Кармайкла

    static int isCarmichaelNumber(int n)

    {

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

            // Если "b" относительно простое число к n

            if (gcd(b, n) == 1)

  

                // И pow (b, n-1)% n не равен 1,

                // вернуть false.

                if (power(b, n - 1, n) != 1)

                    return 0;

        }

        return 1;

    }

  

    // Функция драйвера

    public static void main(String args[])

    {

        System.out.println(isCarmichaelNumber(500));

        System.out.println(isCarmichaelNumber(561));

        System.out.println(isCarmichaelNumber(1105));

    }

}
// Этот код предоставлен Никитой Тивари.

питон

# Программа Python, чтобы проверить, является ли число
# Кармайкл или нет.

  
# служебная функция для поиска gcd из двух чисел

def gcd( a, b) :

    if (a < b) :

        return gcd(b, a)

    if (a % b == 0) :

        return b

    return gcd(b, a % b)

  
# служебная функция для поиска pow (x, y) под
# данный мод по модулю

def power(x, y, mod) :

    if (y == 0) :

        return 1

    temp = power(x, y / 2, mod) % mod

    temp = (temp * temp) % mod

    if (y % 2 == 1) :

        temp = (temp * x) % mod

    return temp

  

  
# Эта функция получает целое число n и
# находит, если это число Кармайкла

def isCarmichaelNumber( n) :

    b = 2

    while b<n :

          

        # Если "b" относительно простое число для n

        if (gcd(b, n) == 1) :

  

            # И pow (b, n-1)% n не равно 1,

            # вернуть ложь.

            if (power(b, n - 1, n) != 1):

                return 0

        b = b + 1

    return 1

  
# Функция драйвера

print isCarmichaelNumber(500)

print isCarmichaelNumber(561)

print isCarmichaelNumber(1105

  
# Этот код предоставлен Никитой Тивари.

C #

// C # программа для проверки, является ли число
// Кармайкл или нет.

using System;

  

class GFG {

  

    // функция полезности для поиска gcd из

    // два числа

    static int gcd(int a, int b)

    {

        if (a < b)

            return gcd(b, a);

        if (a % b == 0)

            return b;

        return gcd(b, a % b);

    }

  

    // функция полезности для поиска pow (x, y)

    // по заданному модулю

    static int power(int x, int y, int mod)

    {

        if (y == 0)

            return 1;

  

        int temp = power(x, y / 2, mod) % mod;

        temp = (temp * temp) % mod;

  

        if (y % 2 == 1)

            temp = (temp * x) % mod;

  

        return temp;

    }

  

    // Эта функция получает целое число n и

    // находит, если это число Кармайкла

    static int isCarmichaelNumber(int n)

    {

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

            // Если "b" относительно простое число к n

            if (gcd(b, n) == 1)

  

                // И pow (b, n-1)% n не равен 1,

                // вернуть false.

                if (power(b, n - 1, n) != 1)

                    return 0;

        }

        return 1;

    }

  

    // Функция драйвера

    public static void Main()

    {

        Console.WriteLine(isCarmichaelNumber(500));

        Console.WriteLine(isCarmichaelNumber(561));

        Console.WriteLine(isCarmichaelNumber(1105));

    }

}

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

PHP

<?php
// PHP программа для проверки
// номер Кармайкл или нет.

  
// полезная функция для поиска
// жкд из двух чисел

function gcd($a, $b)

{

    if ($a < $b)

        return gcd($b, $a);

    if ($a % $b == 0)

        return $b;

    return gcd($b, $a % $b);

}

  
// полезная функция для поиска
// pow (x, y) по заданному модулю

function power($x, $y, $mod)

{

    if ($y == 0)

        return 1;

    $temp = power($x, $y / 2, $mod) % $mod;

    $temp = ($temp * $temp) % $mod;

    if ($y % 2 == 1)

        $temp = ($temp * $x) % $mod;

    return $temp;

}

  
// Эта функция получает целое число
// n и находит, если это Кармайкл
// число

function isCarmichaelNumber($n)

{

    for ($b = 2; $b <= $n; $b++)

    {

        // Если "b" относительно

        // простое число

        if (gcd($b, $n) == 1)

  

            // И pow (b, n - 1)% n

            // не равно 1, вернуть false.

            if (power($b, $n - 1, $n) != 1)

                return 0;

    }

    return 1;

}

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

echo isCarmichaelNumber(500), " \n";

echo isCarmichaelNumber(561), "\n";

echo isCarmichaelNumber(1105), "\n";

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


Выход :

0
1
1

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

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

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

Номера Кармайкла

0.00 (0%) 0 votes