integer mekar

Pernyataan masalah terdiri daripada menyemak nombor tertentu yang akan dimasukkan sebagai input pengguna jika ia adalah nombor Blum.

A Blum Integer ialah nombor separuh perdana dengan faktor perdana a dan b berbeza dalam bentuk 4t+3, dengan t ialah beberapa integer positif. Semiprima ialah nombor yang merupakan hasil darab tepat dua nombor perdana, atau nombor asli yang mempunyai tepat dua faktor perdana. Untuk semiprima, faktornya mungkin sama.

Jika sebarang nombor N ialah integer blum, ia mesti mempunyai dua faktor sahaja, contohnya N=a*b, bukannya 1 dan nombor itu sendiri serta dua faktor, a dan b mestilah daripada bentuk perdana yang berbeza 4t +3 (untuk sebarang integer positif t).

Beberapa integer blum pertama ialah 21, 33, 57, 69, 77, 93, 129, 133, 141...

Tiada nombor asli yang boleh menjadi integer kabur kerana hasil darab dua faktor bukan perdana (dalam bentuk 4t+3 (iaitu nombor ganjil)) akan sentiasa menjadi nombor ganjil yang lebih besar daripada 20.

Dalam masalah ini, kita akan diberikan nombor N dan kita perlu menyemak sama ada nombor itu adalah integer blum.

Contoh

INPUT : N=57
OUTPUT : yes

Arahan: Nombor yang diberikan dalam input ialah 57. Nombor 57 boleh dinyatakan sebagai hasil darab 19 dan 3 (iaitu 19*3). Oleh kerana kedua-dua faktor adalah nombor perdana yang berbeza bagi bentuk 4t+3.

19=4*4+3, nilai t dalam contoh ini ialah 4.

3=4*0+3, nilai t ialah 0.

Oleh itu, nombor 57 ialah integer blum.

INPUT : N=49
OUTPUT : No

Penjelasan: Nombor yang diberi ialah 49, yang boleh dinyatakan sebagai 7*7. Kerana 7 ialah nombor perdana, tetapi untuk nombor ia mestilah hasil darab dua nombor perdana yang berbeza. Oleh itu, 49 bukan integer kabur.

INPUT : N=35
OUTPUT : No

Penjelasan: Nombor 35 boleh dinyatakan sebagai hasil darab 7 dan 5 (iaitu 7*5). Kedua-dua nombor adalah nombor perdana yang berbeza, 7 adalah dalam bentuk 4t+3, tetapi 5 tidak boleh diwakili sebagai 4t+3 untuk sebarang nilai integer bagi t. Oleh itu, 35 bukan integer samar-samar.

Mari kita fahami algoritma untuk menyemak sama ada nombor itu adalah integer blum.

Algoritma

Untuk menyemak sama ada nombor itu adalah integer blum, kita hanya boleh mencari semua nombor perdana sebelum nombor dan kemudian menyemak sama ada hasil darab dua nombor perdana berbeza dalam bentuk 4t+3 boleh membentuk nombor yang diberikan.

Kami akan menggunakan konsep Ayak Eratosthenes untuk mencari semua nombor perdana hingga nombor N yang diberikan. Sieve of Eratosthenes ialah cara yang paling berkesan untuk mencari bilangan nombor perdana mendahului sebarang nombor N.

• Dalam kaedah ini, kami akan mencipta tatasusunan boolean saiz N+1, dengan N ialah nombor yang diberikan. Jika nombor itu ialah nombor perdana yang nilai indeksnya sama dengan nombor ini, kami akan menyimpan benar, jika tidak kami akan menyimpan palsu dalam tatasusunan.

• Untuk mengemas kini nilai indeks palsu yang sepadan dengan nombor bukan perdana sehingga N, kami akan lelaran daripada i=2 kepada i<=sqrt(N) dalam gelung for, kerana sebarang nombor kurang daripada atau sama dengan N, jika Ia bukan perdana, ia mesti mempunyai faktor dalam julat [2, sqrt(N)]. <=sqrt(N)，因为任何小于或等于 N 的数字，如果它不是质数，则必须有一个位于 [2, sqrt(N)] 范围内的因子。

• Jika nilai arr[i] sepadan dengan i adalah benar, kami akan lelaran daripada p=i*i dalam gelung bersarang sehingga p<=N, dan pada semua gandaan seterusnya p kemas kini palsu . Jika ia adalah palsu pada nilai yang sepadan i, kita lelaran kepada nilai seterusnya i. <=N，并在 p 的所有下一个倍数处更新 false。如果在 i 的相应值处为 false，我们将迭代 i 的下一个值。

Menggunakan penapis Eratosthenes, kita boleh mendapatkan semua nombor perdana dari 1 hingga N. Sekarang, lelaran dalam gelung for dalam tatasusunan, kita akan menyemak sama ada terdapat sebarang nombor perdana yang merupakan faktor nombor N yang diberikan dan dalam bentuk 4t+3 dan hasil bagi nombor perdana dibahagikan dengan N juga daripada bentuk 4t+3 Nombor perdana berbeza. Nombor N yang diberikan akan menjadi integer blum jika semua syarat di atas dipenuhi, jika tidak, ia tidak.

Kami akan menggunakan algoritma ini dalam pendekatan kami untuk menyelesaikan masalah dengan cekap.

kaedah

Diberikan di bawah adalah langkah-langkah untuk melaksanakan algoritma dalam pendekatan kami untuk menyemak sama ada N ialah integer blum -

• Kami akan mencipta fungsi untuk menyemak sama ada nombor itu adalah integer blum.

• Dalam fungsi, menggunakan konsep ayak Eratosthenes, kami menyimpan benar untuk semua nombor perdana dalam tatasusunan boolean saiz N+1 sehingga N pada indeks yang sepadan.

• Lelaran daripada i=2 hingga i<=N dalam gelung for untuk menyemak sama ada sebarang nombor perdana bagi bentuk 4t+3 ialah faktor nombor yang diberikan. <=N，以检查 4t+3 形式的任何素数是否是给定数字的因子。

• Jika kita menemui sebarang nombor perdana yang merupakan faktor N dalam bentuk 4t+3, kita akan menyimpan hasil bagi N dibahagikan dengan nombor perdana itu.

• Kami akan mengembalikan benar jika hasil bagi juga perdana dan dalam bentuk 4t+3, palsu sebaliknya.

• Jika fungsi kembali benar, nombor itu ialah integer blum.

Contoh

C++ kod kaedah ini -

// C++ program to check if the number is a blum integer or not
#include <bits/stdc++.h>

using namespace std;

// to check if N is a blum integer or not
bool check(int N){
   bool a[N + 1]; //to store true corresponding to the index value equal to prime number
    memset(a,true,sizeof(a));

   // to update the array with false at index value corresponding to non prime numbers
   for (int i = 2; i<=sqrt(N); i++) {

      //if i is a prime number
      if (a[i] == true) {

         //updating false at all the multiples of i less than or equal to N from i*i
         for (int p = i * i; p <= N; p += i)
            a[p] = false;
      }
   }

   //to check if there exist distinct prime numbers whose product is equal to N
   for (int i = 2; i <= N; i++) {
      if (a[i]) {

          //if i is the prime factor of the form 4t+3
         if ((N % i == 0) && ((i - 3) % 4) == 0) {
            int quotient = N / i;
            //to check if quotient*i=N and both are distinct prime numbers of form 4t+3
            if(quotient!=i && a[quotient] && (quotient-3)%4==0){
                return true;
            } else {
               return false;
            }
         }
      }
   }
   return false;
}
int main(){
   
   int N;
   N=469;
   //calling the function
   if (check(N)==true) //if function returns true, it is a blum integer
      cout <<N<<" is a blum integer."<<endl;
   else
      cout <<N<<" is not a blum integer."<<endl;
   return 0;
}

Output

469 is a blum integer.

Kerumitan masa: O(N*log(log(N)), kerana ia adalah kerumitan masa penapis Eratosthenes.

Kerumitan ruang: O(N) kerana kami menggunakan tatasusunan saiz N+1 untuk menyimpan nombor perdana.

Kesimpulan

Konsep integer blum dibincangkan dalam artikel. Dalam artikel ini, kami mencadangkan cara yang cekap untuk menyemak sama ada nombor ialah integer blum menggunakan konsep Ayak Eratosthenes dalam C++.

Semoga selepas membaca artikel ini, anda telah memahami dengan jelas konsep integer blum dan mempelajari kaedah untuk menyemak sama ada nombor tersebut adalah integer blum.

Atas ialah kandungan terperinci integer mekar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!