İşlemcinizi asal sayı test programı ile test edin.

John Ahmet

MB Üyesi
Kayıt
23 Ağustos 2017
Mesajlar
50
Tepkiler
16
Yaş
44
Üniv
Ege Universitesi
Asal sayıları seri halinde bulan bir kod hazırladım. Bir milyardan küçük asal sayıları bulmak için intel Core i7 türünde bir işlemciye ve 8 GB RAM' e sahip bilgisayarımda işlem yaklaşık 18 saniye sürdü. Bu programın işlemcinizi çok fazla yoracağını iddia etmiyorum aksine en az şekilde yorarak en fazla asal sayıyı bulma üzerine çalışıldı.

Ayrıca isPrime ve isBigPrime isimli iki static method daha büyük asal sayıları bulmak için hazırlandı.

Sizin bilgisayarınızda işlem ne kadar sürecek paylaşabilir misiniz?

Sadece Exe dosyası arşiv halinde;
Linki görmek için izniniz yoktur Giriş yap veya kayıt ol.



Tüm kodlar;
Linki görmek için izniniz yoktur Giriş yap veya kayıt ol.



Kod:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Numerics;

namespace TestPrimes
{
     /***************************************************************************************
     * Bu program asal sayıları çok kısa sürede bulabilmektedir.                            *
     * Ayhan ARICAN tarafından yazıldı. Görüş ve önerileriniz için email: a.arican@msn.com  *
     * *************************************************************************************/
    class Program
    {
        static void Main(string[] args)
        {
            // Eğer RAM iniz yeterli ise limit değeri en fazla int.MaxValue - 56 olabilir (2.147.483.592).
            ulong limit = 1000000000; /// bir milyardan küçük asal sayılar bulunacak.

            Console.WriteLine();
            Console.WriteLine("Lütfen bekleyin {0} sayısından küçük asal sayılar bulunuyor...", limit);
            Console.WriteLine();
            try
            {
                var primes = new Primes(limit); // limit değerinden küçük asal sayıları bulup primes değişkenine atar.


                Console.WriteLine("{0} sayısından küçük {1} asal sayı bulundu. İşlem süresi : {2:t} ", limit, primes.Count, primes.CalculationDuration);
            }
            catch (OutOfMemoryException oome)
            {
                Console.WriteLine("İşlemi gerçekleştirmek için belleğiniz yeterli değil limit değerini küçültüp bir daha deneyin.");
            }
            catch(Exception e)
            {
                Console.WriteLine("Beklenmeyen bir hata oluştu.");
            }

            /* **************************************************************************
             * Sayıları ekrana yazdırır. Yazdırma süresi işlem süresine dahil değildir. *
             ****************************************************************************/
            //foreach (var prime in primes)
            //Console.WriteLine(prime);

            var number = ulong.MaxValue - 4; // 2 ^ 64 - 5 = 18.446.744.073.709.551.611

            Console.WriteLine();
            Console.WriteLine("{0} sayısı asal{1}", number, isPrime(number) ? "dır" : " değildir");

            var number2 = BigInteger.Parse("654654669654646464654654664646464464646461");

            Console.WriteLine();
            Console.WriteLine("{0} sayısı asal{1}", number2, isBigPrime(number2) ? "dır" : " değildir");

            Console.WriteLine();
            Console.WriteLine("Programa son vermek için [Enter] tuşuna basın.");
            Console.WriteLine();

            Console.ReadLine();
        }

        public static bool isPrime(ulong n)
        {
            // Küçük sayılar için test yapılıyor
            if (n <= 1) return false;
            if (n <= 3) return true;

            // 25 ten küçük sayılar, asal değilse 2 yada 3 'e kesinlikle bölünür. ((i * i <= n) i = 5 ten başlıyor.)
            if (n % 2 == 0 || n % 3 == 0) return false;
        
            // 3 ten büyük tüm asal sayılar k bir tamsayı olmak üzere 6k - 1 yada 6k + 1 olarak ifade edilebilir.
            // Bu nedenle hız kazanmak için döngüye 6'şar artırılarak devam ediliyor.
            for (ulong i = 5; i * i <= n; i = i + 6)
                if (n % i == 0 || n % (i + 2) == 0)
                    return false;

            return true;
        }

        public static bool isBigPrime(BigInteger n)
        {
            if (n <= ulong.MaxValue)
                return isPrime((ulong)n);
            // Fermat teoremine göre p asal bir sayı ise a ^ (p - 1) mod p = 1 dir.
            // Hesaplamanın kolay olması için a yı 2 alıyoruz.
            // Eğer 2 ^ (n - 1) mod n != 1 den n asal olamaz diyoruz false döndürüyoruz.
            // 2 ^ (n - 1) % n != 1 ise (ModPow methodu bu işlemi çok hızlı yapmaktadır)
            else if (BigInteger.ModPow(2, n - 1, n) != 1)
                return false;
            else
            {
                // 2 ^ (n - 1) mod n == 1 ise bu n ' nin kesinlikle asal olduğu anlamına gelmiyor.
                // Ancak büyük ihtimalle asaldır diyebiliriz.
                // Yine de kesin bir sonuç için test işlemine devam ediyoruz.
                Console.WriteLine("{0} sayısı büyük ihtimalle asal sayı, bu nedenle kesin çözüm için test işlemi uzun sürebilir.", n);

                // 2 ye yada 3 e bölünebiliyorsa false değerini döndürüyoruz.
                if (n % 2 == 0 || n % 3 == 0) return false;

                BigInteger i = 5;

                while (i * i <= n)
                {
                    if (n % i == 0 || n % (i + 2) == 0)
                        return false;
                    // Tüm asal sayılar 6k - 1 yada 6k + 1 olarak ifade edilebilir.
                    // Bu nedenle hız kazanmak için döngüye 6'şar artırılarak devam ediliyor.
                    i += 6;
                }

                return true;
            }
        }
    }

    public class Primes : IEnumerable<ulong>
    {
        private ulong limit;
        private ulong count;
        private bool[] numbers;
        private DateTime startTime;
        private TimeSpan calculatationDuration;

        public Primes(ulong limit)
        {
            this.count = 0;
            this.limit = limit;
            this.numbers = new bool[limit];
            startTime = DateTime.Now;
            findPrimes(); // limit değerinden küçük bütün asallar bu method ile bulunuyor.
            calculatationDuration = DateTime.Now - startTime; // süre hesaplanıyor
        }

        private void findPrimes()
        {
            // Şu an numbers dizisinin tüm elemanları false değerindedir.
            // limitten küçük bütün tek sayılar true yapılıyor (1 hariç çünkü artık asal olarak kabul edilmiyor).
            for (ulong i = 3; i < limit; i += 2) numbers[i] = true;
            // 2 çift olan yegane asal sayıdır (özel durum).
            if (limit > 2) numbers[2] = true;
            // 3 ten itibaren bütün tek sayılar dolaşılıyor.
            for (ulong j = 3; j * j <= limit; j += 2)
            {
                if (numbers[j])//is true
                    // Tek sayıların tek katları asal olmadığından değerler false yapılıyor.
                    for (ulong p = 3; (p * j) < limit; p += 2)
                        numbers[p * j] = false;
            }
        }

        public IEnumerator<ulong> GetEnumerator()
        {
            for(ulong i = 2; i < 3; i++)
                if (numbers[i])
                    yield return i;
            for (ulong i = 3; i < limit; i+=2)
                if (numbers[i])
                    yield return i;
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }


        public ulong Count
        {
            get
            {
                if (count == 0)
                {
                    if (limit > 2) count++;
                    for (ulong i = 3; i < limit; i += 2)
                        if (numbers[i]) count++;

                    return count;
                }
                else return count;
            }
        }

        public bool[] Numbers { get { return numbers; } }
        public TimeSpan CalculationDuration { get { return calculatationDuration; } }
    }
}
 
Son düzenleme:

Atakan Akbulut

Yetkili Kişi
Moderatör
Kayıt
28 Nisan 2016
Mesajlar
143
Tepkiler
43
Meslek
R&D Embedded Systems Software Engineer
2 bilgisayar 1 geliştirme boardım var hepside linux :)
 
Konu sahibi
Konu sahibi
John Ahmet

John Ahmet

MB Üyesi
Kayıt
23 Ağustos 2017
Mesajlar
50
Tepkiler
16
Yaş
44
Üniv
Ege Universitesi
2 bilgisayar 1 geliştirme boardım var hepside linux :)
Talep ederseniz kodu node.js ile yazabilirim ne diyorsunuz? Node.JS işinizi görür mü? Geliştirme board unuz Ardunio destekli ise Proccessing ile deneyebiliriz ancak bu yöntem için hafıza yeterli olmaz. Sieve yerine ulong türünde test yapan isPrime methodunu alsanız board da işinizi görebilir.
 
Yukarı Alt