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

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

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