Demək olar ki, sadə ədədlər#1302

Demək olar ki, sadə ədədlər (Həll təhlili)

Demək olar ki, sadə sayılar $p^{k}$ p^k şəklində olan natural ədədlərdir, burada $p$ sadə ədəd, $k \geq 2$ k \ge 2-dir. Məsələn, demək olar ki, sadə ədədlər: $4, 8, 16, 32, 9, 81, ...$ 4, 8, 16, 32, 9, 81, ... .

Çünki $hi g h < 1 0^{12}$ high < 10^{12}, demək olar ki, sadə ədədin tərifinə əsasən, sadə sayı $p$ üçün mümkün olan qiymətlər $p < 1 0^{6}$ p < 10^6 verilmiş qeyri-bərabərliyə uyğundur.

Uzunluğu $1 0^{6}$ 10^6 olan $p r im es$ massivini yaradaq, burada $p r im es [i] = 1$ primes[i] = 1, əgər $i$ sadə ədəddirsə, əks halda $p r im es [i] = 0$ primes[i] = 0.

Daha sonra $1 0^{12}$ 10^{12}-ni aşmayan bütün demək olar ki, sadə ədədləri əhatə edən $m$ massivini düzəldək. Belə ədədlərin sayı $80070$ təşkil edir və onları artan qaydada sıralayırıq.

$a, b$ aralığında demək olar ki, sadə ədədlərin sayını $f (a, b)$ f(a, b) kimi işarə edək. O zaman

f (l o w, hi g h) = f (1, hi g h) - f (1, l o w - 1)

f(low, high) = f(1, high) - f(1, low - 1)

$[1.. n]$ aralığında demək olar ki, sadə ədədlərin sayı $m$ massivinin nizamını qorumaq üçün $n$ ədədinin yerləşdirilə biləcəyi indeksə bərabərdir.

Bu indeksi binar axtarış vasitəsilə - upper_bound funksiyası ilə tapmaq olar.

Nümunə

$1$ -dən $100$ -ə qədər aralıqda bütün demək olar ki, sadə ədədləri yaradasaq.

Əvvəlcə $100$ -ü aşmayan $2$ sadə ədədinin qüvvətlərini yazaq:

4, 8, 16, 32, 64

4, 8, 16, 32, 64

Sonra $3$ qüvvətlərini yazaq:

9, 27, 81

9, 27, 81

Sonra $5$ qüvvətlərini:

25

Nəhayət, $7$ qüvvətlərini yazaq:

49

$11$ -in kvadratı $121$ bərabərdir və bu, $100$ -dən çoxdur, buna görə $11$ və yuxarı qüvvətlər verilmiş diapazona düşmür.

Sıralanandan sonra massiv:

İkinci testə baxaq: $[1; 20]$ . Bu aralıqda aşağıdakı demək olar ki, sadə ədədlər var: $4, 8, 9, 16$ 4, 8, 9, 16. Onların sayı $4$ -ə bərabərdir.

Alqoritmin reallaşdırılması

Qlobal massivlər elan edəcəyik. Doğrudan böyük olmayan demək olar ki, sadə ədədlər $M A X = 1 0^{6}$ MAX = 10^6-dən böyük olmayan sadə ədədlərin qüvvətləridir.

Tapılan bütün demək olar ki, sadə ədədləri $m$ massivində saxlayacağıq.

#define MAX 1000010
char primes[MAX];
long long m[MAX];

Ədədlərin sadəliyini yoxlamaq üçün əvvəlcədən $p r im es$ massivini yaradaq.

void gen_primes(void)
{
  for (int i = 0; i < MAX; i++) primes[i] = 1;
  for (int i = 2; i < sqrt(MAX); i++)
    if (primes[i])
      for (int j = i * i; j < MAX; j += i) primes[j] = 0;
}

C++

Proqramın əsas hissəsi.

gen_primes();

Hər bir sadə sayı $i$ üçün onun qüvvətlərini $i^{2}, i^{3}, i^{4}, ...$ i^2, i^3, i^4, ... ardıcıl olaraq $1 0^{12}$ 10^{12}-ni aşmadığı müddətcə $m$ massivinə əlavə edirik. $pt r$ dəyişəni, $m$ massivinə əlavə edilmiş demək olar ki, sadə ədədlərin sayını saxlayır. Çünki demək olar ki, sadə ədədlərin dəyərləri $1 0^{12}$ 10^{12}-dən çox deyil, saxlamaq və hesablama üçün $64$ bitlik tam ədədlərdən (long long tipindən) istifadə etməlisiniz.

for(i = 2; i < MAX; i++)
  if (primes[i])
  {
    long long temp = 1LL*i*i;
    while(temp < 1LL*MAX*MAX)
    {  
      m[ptr++] = temp;
      temp *= i;
    }
  }

C++

STL standart kitabxanası ilə $m$ massivini sıralayırıq.

sort(m,m+ptr);

Daxil testlərinin sayını $t es t s$ oxuyuruq və hər bir aralıq üçün $[l, h]$ dəyərini hesablamaq və çap etmək üçün

f (l, h) = f (1, h) - f (1, l - 1)

f(l, h) = f(1, h) - f(1, l - 1)

Hər bir belə sorğu $O (l o g_{2} pt r)$ O(log_2~ptr) vaxtında binar axtarış vasitəsilə işlənir.

scanf("%d", &tests);
while(tests--)
{
  scanf("%lld %lld", &l, &h);
  printf("%d\n", upper_bound(m,m+ptr,h) - upper_bound(m,m+ptr,l-1));
}

Java reallaşdırılması

import java.util.*;

public class Main
{
  public static ArrayList<Long> primes = new ArrayList<Long>();
  
  public static void GenPrimes()
  {
    final int MAX_SIZE = 1000001;	  
    BitSet bits = new BitSet(MAX_SIZE);

    bits.set(2, MAX_SIZE, true);
    for (int i = 2; i < Math.sqrt(MAX_SIZE); i++) 
    {
      if (bits.get(i)) 
        for (int j = i * i; j < MAX_SIZE; j += i) 
          bits.set(j, false);
    }
    
    for (int i = 2; i < MAX_SIZE; i++)
      if (bits.get(i))
      {
        long temp = i;
        while ((temp *= i) < 1000000000000L) 
          primes.add(temp);
      }
    primes.add(1000000000001L);
    Collections.sort(primes);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int tests = con.nextInt();
    GenPrimes();
    
    for(int i = 0; i < tests; i++)
    {
      Long low = con.nextLong();
      Long high = con.nextLong();
      int lIndex = Collections.binarySearch(primes, low);
      if (lIndex < 0) lIndex = -(lIndex + 1);
      int hIndex = Collections.binarySearch(primes, high);
      if (hIndex < 0) hIndex = -(hIndex + 1); else hIndex++; 

      System.out.println(hIndex - lIndex);
    }
  }
}

Java