April 25

Merhaba,

D'de (sanırım) size asal sayı dizisi veren hazır bir algoritma yok. Geçenlerde hız testleri yapmak için (belki siz kriptolojide kullanmak istersiniz) hazır ve basit algoritma aradım bulamadım. Aklıma ilk şurası geldi:

https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Extensible_Version

Ama ya çok karışıklar ya da yeterince iyi değiller, hatta eskiler! İhtiyacım olan şöyle bir şey:

bool isPrime(T)(T n) pure
{
  if(n <= 1) return false;
  if(n <= 3) return true;
  if(n % 2 == 0 || n % 3 == 0) return false;

  for(auto i = size_t(5); i * i <= n; i += size_t(6))
  {
    if(n % i == 0 || n % (i + 2) == 0)
    {
      return false;
    }
  }
  return true;
}

İsmi ve yaptığı çok güzel. Her yerde işinize yarar ama yetmez! Çünkü küçük bir liste için bakınız tonlarca şeye ihtiyacınız var:

alias type = uint;
enum limit = 25;
import std;

void main()
{
  iota(type.max).filter!(a => a.isPrime)
                .take(limit)
                .writeln;
} /* ÇIKTISI:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
//*/

Tamam biraz abartmış olabilirim! Yine de sayalım: iota, filter, take ve import ile modülleri eklemek gerek. Yani ilk 25 asal sayıyı yazmak için yorucu sanki, peki şu yardımcı araç ile güzel bir ikili oluşturabilirler mi?

auto sieve(T)(T limit, T first = 1)
in(limit > 0 && first > 0, "SIFIR OLMAMALI") {
  T[] list;
  do if(first.isPrime) {
    list ~= first;
    if(--limit == 0) break;
  } while(++first > 0);
  return list;
}

Hem de tadından yenmez çünkü 2 parametre alıyor. Diyelim ki 100'den sonraki asal sayılara ihtiyacınız var, işte bu kadar basit:

  limit.sieve(100).writeln;

  // [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229]

Seçim sizin! Elbette aynı çıktıyı standart kütüphanedeki bazı işlevlerle de yapabilirsiniz. Örneğin ilk verdiğim senaryoyu 100.iota(type.max) şeklinde değiştirirseniz ikinci ile aynı olacaktır.

Son olarak BONUS:

RosettaCode'da yer alan 'Extensible Version' çok karışıktı, biraz düzenledim. Benzer şeyleri yapma yeteneğine opCall() ve ekstra skip değişkeni sayesinde bu yapı da sahip:

alias Sieve = ExpandingFactors;
struct ExpandingFactors(T)
{
  T[] list;

  auto opCall(in T n)
  {
    if(list.empty) list ~= 2;
    while(n >= list.length) next();
    return list[n];
  }

  void next()
  {
    auto last = list[$ - 1] + 1;
    auto buff = new bool[last];
    // Disabling candidates
    T n;
    foreach(p; list)
    {
      n = last / p * p;
      if (n < last) n += p;
      for(n -=last; n < buff.length; n += p)
      {
        buff[n] = true;
      }
    }
    // Expanding factors
    n = 0;
    while (n < buff.length)
    {
      if (!buff[n]) list ~= last + n;
      ++n;
    }
  }
}

alias type = uint;
enum limit = 25;
import std;

void main()
{
  Sieve!type primes;

  auto skip = 50; // ilk 50 asalı atla
  skip.iota(limit + skip)
      .map!primes
      .writeln;
} /* ÇIKTISI:
[233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379]
//*/

SDB@79

May 12

On Thursday, 25 April 2024 at 21:17:50 UTC, Salih Dincer wrote:

>

Merhaba,

D'de (sanırım) size asal sayı dizisi veren hazır bir algoritma yok...

Sanırım aşağıdaki gibi bir kod da dünya yüzeyinde yoktu ama artık var:

Çok çok iyi optimize edilmiş, kısa ve hızlı kod karşınızda. Olur ya ikiz kardeşlere ihtiyaç duyarsınız:

void main()
{
  printTwinPrimeList!3825; // ilk 100 ikiz asal sayıları ekrana listeler
}

void printTwinPrimeList(size_t limit)()
{
  auto primes = [3];

  bool test(int num) {
    foreach (prime; primes) {
      if (prime * prime > num) break;
      if (num % prime == 0) return false;
    }
    return true;
  }

  import std.stdio : writeln;

  auto num = 5;
  while (num < limit) {
    if (test(num)) {
      primes ~= num;
      if (num - primes[$ - 2] == 2) {
        writeln(primes[$ - 2], " ", num);
      }
    }
    num += 2;
  }
}

SDB@79