أجمل طريقة توليد الأعداد [مغلقة]

Question

ما هي الطريقة الأكثر أناقة لتنفيذ هذه الوظيفة:

ArrayList generatePrimes(int n)

هذه الوظيفة يولد الأولى n يعبي (تحرير:حيث n>1) ، وذلك generatePrimes(5) سوف يعود ArrayList مع {2, 3, 5, 7, 11}.(أنا أفعل هذا في C#, ولكن أنا سعيد مع تنفيذ جافا أو أي صيغة مشابهة في هذا الشأن (حتى لا هاسكل)).

أنا لا أعرف كيف أكتب هذه الوظيفة ، ولكن عندما فعلت الليلة الماضية لم ينتهي لطيفا كما كنت آمل.هنا هو ما جئت به:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();
    primes.Add(2);
    primes.Add(3);
    while (primes.Count < toGenerate)
    {
        int nextPrime = (int)(primes[primes.Count - 1]) + 2;
        while (true)
        {
            bool isPrime = true;
            foreach (int n in primes)
            {
                if (nextPrime % n == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                break;
            }
            else
            {
                nextPrime += 2;
            }
        }
        primes.Add(nextPrime);
    }
    return primes;
}

أنا لست قلقة جدا من سرعة, على الرغم من أنني لا أريد أن يكون من الواضح عدم الكفاءة.لا العقل الذي يستخدم طريقة (السذاجة أو غربال أو أي شيء آخر) ، ولكن أنا لا أريد أن تكون قصيرة نسبيا و من الواضح كيف يعمل.

تحرير:شكرا لكل من أجاب على الرغم من أن الكثيرين لم تجيب على السؤال الفعلي.أن أكرر أردت لطيفة نظيفة قطعة من التعليمات البرمجية التي ولدت قائمة من الأعداد الأولية.بالفعل أنا أعرف كيف نفعل ذلك مجموعة من الطرق المختلفة, ولكن أنا عرضة كتابة التعليمات البرمجية التي ليست واضحة كما يمكن أن يكون.في هذا الموضوع عدد قليل من الخيارات الجيدة المقترحة:

• أجمل نسخة من ما كان في الأصل (بيتر سميت ، jmservera و Rekreativc)
• نظيفة جدا تنفيذ غربال إراتوستينس (starblue)
• استخدام جافا BigIntegers nextProbablePrime للحصول على رمز بسيط جدا, على الرغم من أنني لا أتخيل أن يكون فعالة بشكل خاص (dfa)
• استخدام LINQ إلى بتكاسل توليد قائمة من الأعداد الأولية (Maghis)
• وضع الكثير من يعبي في ملف نصي وقراءتها عند الضرورة (دارين)

تحرير 2:لقد نفذت في C# اثنين من الأساليب الواردة هنا و هناك طريقة أخرى غير المذكورة هنا.كانت أول n يعبي بشكل فعال (ولدي لائق طريقة العثور على الحد الأقصى لتوفير إلى المناخل).

Answer 1

شكرا جزيلا لجميع الذين قدموا إجابات مفيدة.فيما يلي تطبيقاتي لبعض الطرق المختلفة للعثور على الأول ن الأعداد الأولية في C #.الطريقتان الأوليان هما إلى حد كبير ما تم نشره هنا.(أسماء الملصقات موجودة بجوار العنوان.) أخطط للقيام بغربلة أتكين في وقت ما، على الرغم من أنني أظن أنها لن تكون بسيطة تمامًا مثل الطرق الموجودة هنا حاليًا.إذا كان بإمكان أي شخص رؤية أي طريقة لتحسين أي من هذه الأساليب، فأنا أرغب في معرفتها :-)

الطريقة القياسية (بيتر سميت, com.jmservera, ريكرياتيفك)

الرقم الأولي الأول هو 2أضف هذا إلى قائمة الأعداد الأولية.العدد الأولي التالي هو الرقم التالي الذي لا يقبل القسمة على أي رقم في هذه القائمة.

public static List<int> GeneratePrimesNaive(int n)
{
    List<int> primes = new List<int>();
    primes.Add(2);
    int nextPrime = 3;
    while (primes.Count < n)
    {
        int sqrt = (int)Math.Sqrt(nextPrime);
        bool isPrime = true;
        for (int i = 0; (int)primes[i] <= sqrt; i++)
        {
            if (nextPrime % primes[i] == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes.Add(nextPrime);
        }
        nextPrime += 2;
    }
    return primes;
}

وقد تم تحسين ذلك من خلال اختبار قابلية القسمة على الجذر التربيعي للرقم الذي يتم اختباره فقط؛وعن طريق اختبار الأرقام الفردية فقط.يمكن تحسين ذلك بشكل أكبر عن طريق اختبار أرقام النموذج فقط 6k+[1, 5], ، أو 30k+[1, 7, 11, 13, 17, 19, 23, 29] أو قريباً.

غربال إراتوستينس (com.starblue)

هذا يجد كل الأعداد الأولية ل ك.لعمل قائمة بالأولى ن الأعداد الأولية، نحتاج أولاً إلى تقريب القيمة نرئيس الوزراء.الطريقة التالية، كما هو موضح هنا, يفعل هذا.

public static int ApproximateNthPrime(int nn)
{
    double n = (double)nn;
    double p;
    if (nn >= 7022)
    {
        p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
    }
    else if (nn >= 6)
    {
        p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
    }
    else if (nn > 0)
    {
        p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
    }
    else
    {
        p = 0;
    }
    return (int)p;
}

// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
    BitArray bits = new BitArray(limit + 1, true);
    bits[0] = false;
    bits[1] = false;
    for (int i = 0; i * i <= limit; i++)
    {
        if (bits[i])
        {
            for (int j = i * i; j <= limit; j += i)
            {
                bits[j] = false;
            }
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfEratosthenes(limit);
    List<int> primes = new List<int>();
    for (int i = 0, found = 0; i < limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(i);
            found++;
        }
    }
    return primes;
}

غربال سوندارام

لقد اكتشفت فقط هذا المنخل في الآونة الأخيرة، ولكن يمكن تنفيذها بكل بساطة.تنفيذي ليس بنفس سرعة غربال إراتوستينس، لكنه أسرع بكثير من الطريقة الساذجة.

public static BitArray SieveOfSundaram(int limit)
{
    limit /= 2;
    BitArray bits = new BitArray(limit + 1, true);
    for (int i = 1; 3 * i + 1 < limit; i++)
    {
        for (int j = 1; i + j + 2 * i * j <= limit; j++)
        {
            bits[i + j + 2 * i * j] = false;
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfSundaram(limit);
    List<int> primes = new List<int>();
    primes.Add(2);
    for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(2 * i + 1);
            found++;
        }
    }
    return primes;
}

Answer 2

استخدم التقدير

pi(n) = n / log(n)

لعدد الأعداد الأولية يصل إلى n للعثور على حد، ثم استخدم الغربال.يقلل التقدير من عدد الأعداد الأولية حتى n إلى حد ما، لذلك سيكون الغربال أكبر قليلاً من اللازم، وهذا أمر جيد.

هذا هو منخل جافا القياسي الخاص بي، والذي يحسب أول مليون عدد أولي في حوالي ثانية واحدة على جهاز كمبيوتر محمول عادي:

public static BitSet computePrimes(int limit)
{
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++)
    {
        if (primes.get(i))
        {
            for (int j = i * i; j < limit; j += i)
            {
                primes.clear(j);
            }
        }
    }
    return primes;
}

Answer 3

إعادة إحياء سؤال قديم، لكنني تعثرت فيه أثناء اللعب مع LINQ.

يتطلب هذا الرمز .NET4.0 أو .NET3.5 مع ملحقات متوازية

public List<int> GeneratePrimes(int n) {
    var r = from i in Enumerable.Range(2, n - 1).AsParallel()
            where Enumerable.Range(2, (int)Math.Sqrt(i)).All(j => i % j != 0)
            select i;
    return r.ToList();
}

Answer 4

أنت على الطريق الجيد.

بعض التعليقات

• الأعداد الأولية.إضافة(3);يجعل هذه الوظيفة لا تعمل مع الرقم = 1

• ليس عليك اختبار القسمة بأعداد أولية أكبر من الجذر التربيعي للرقم المطلوب اختباره.

الكود المقترح:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();

    if(toGenerate > 0) primes.Add(2);

    int curTest = 3;
    while (primes.Count < toGenerate)
    {

        int sqrt = (int) Math.sqrt(curTest);

        bool isPrime = true;
        for (int i = 0; i < primes.Count && primes.get(i) <= sqrt; ++i)
        {
            if (curTest % primes.get(i) == 0)
            {
                isPrime = false;
                break;
            }
        }

        if(isPrime) primes.Add(curTest);

        curTest +=2
    }
    return primes;
}

Answer 5

يجب عليك إلقاء نظرة على الأعداد الأولية المحتملة.على وجه الخصوص نلقي نظرة على الخوارزميات العشوائية و اختبار ميلر-رابين للأولوية.

من أجل الاكتمال يمكنك فقط استخدام java.math.BigInteger:

public class PrimeGenerator implements Iterator<BigInteger>, Iterable<BigInteger> {

    private BigInteger p = BigInteger.ONE;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public BigInteger next() {
        p = p.nextProbablePrime();
        return p;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public Iterator<BigInteger> iterator() {
        return this;
    }
}

@Test
public void printPrimes() {
    for (BigInteger p : new PrimeGenerator()) {
        System.out.println(p);
    }
}

Answer 6

ليست فعالة بأي حال من الأحوال، ولكن ربما الأكثر قابلية للقراءة:

public static IEnumerable<int> GeneratePrimes()
{
   return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
                                     .All(divisor => candidate % divisor != 0));
}

مع:

public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
   for (int i = from; i <= to; i++) yield return i;
}

في الواقع مجرد اختلاف في بعض المشاركات هنا بتنسيق أجمل.

Answer 7

أعلم أنك طلبت حلاً غير هاسكل ولكنني أدرج هذا هنا من حيث صلته بالسؤال وأيضًا هاسكل جميلة لهذا النوع من الأشياء.

module Prime where

primes :: [Integer]
primes = 2:3:primes'
  where
    -- Every prime number other than 2 and 3 must be of the form 6k + 1 or 
    -- 6k + 5. Note we exclude 1 from the candidates and mark the next one as
    -- prime (6*0+5 == 5) to start the recursion.
    1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n      = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p    = n `mod` p == 0

Answer 8

استخدم رئيس الوزراء مولد الأرقام لإنشاء primes.txt ثم:

class Program
{
    static void Main(string[] args)
    {
        using (StreamReader reader = new StreamReader("primes.txt"))
        {
            foreach (var prime in GetPrimes(10, reader))
            {
                Console.WriteLine(prime);
            }
        }
    }

    public static IEnumerable<short> GetPrimes(short upTo, StreamReader reader)
    {
        int count = 0;
        string line = string.Empty;
        while ((line = reader.ReadLine()) != null && count++ < upTo)
        {
            yield return short.Parse(line);
        }
    }
}

في هذه الحالة، أستخدم Int16 في توقيع الطريقة، لذلك يحتوي ملف primes.txt الخاص بي على أرقام من 0 إلى 32767.إذا كنت تريد توسيع هذا إلى Int32 أو Int64، فقد يكون ملف primes.txt الخاص بك أكبر بكثير.

Answer 9

يمكنني تقديم الحل C# التالي.إنها ليست سريعة بأي حال من الأحوال، ولكن من الواضح جدًا ما تفعله.

public static List<Int32> GetPrimes(Int32 limit)
{
    List<Int32> primes = new List<Int32>() { 2 };

    for (int n = 3; n <= limit; n += 2)
    {
        Int32 sqrt = (Int32)Math.Sqrt(n);

        if (primes.TakeWhile(p => p <= sqrt).All(p => n % p != 0))
        {
            primes.Add(n);
        }
    }

    return primes;
}

لقد تركت أي شيكات - إذا كان الحد سالبًا أو أصغر من اثنين (في الوقت الحالي، ستعيد الطريقة دائمًا اثنين على الأقل كعدد أولي).ولكن هذا كله سهل الإصلاح.

تحديث

مع طريقتي التمديد التاليتين

public static void Do<T>(this IEnumerable<T> collection, Action<T> action)
{
    foreach (T item in collection)
    {
        action(item);
    }
}

public static IEnumerable<Int32> Range(Int32 start, Int32 end, Int32 step)
{
    for (int i = start; i < end; i += step)
    }
        yield return i;
    }
}

يمكنك إعادة كتابته على النحو التالي.

public static List<Int32> GetPrimes(Int32 limit)
{
    List<Int32> primes = new List<Int32>() { 2 };

    Range(3, limit, 2)
        .Where(n => primes
            .TakeWhile(p => p <= Math.Sqrt(n))
            .All(p => n % p != 0))
        .Do(n => primes.Add(n));

    return primes;
}

إنها أقل كفاءة (لأن الجذر التربيعي يتم إعادة تقييمه في كثير من الأحيان) ولكنه كود أكثر نظافة.من الممكن إعادة كتابة الكود لتعداد الأعداد الأولية بتكاسل، لكن هذا سيؤدي إلى فوضى في الكود قليلاً.

Answer 10

وهنا تنفيذ غربال إراتوستينس شركة#:

    IEnumerable<int> GeneratePrimes(int n)
    {
        var values = new Numbers[n];

        values[0] = Numbers.Prime;
        values[1] = Numbers.Prime;

        for (int outer = 2; outer != -1; outer = FirstUnset(values, outer))
        {
            values[outer] = Numbers.Prime;

            for (int inner = outer * 2; inner < values.Length; inner += outer)
                values[inner] = Numbers.Composite;
        }

        for (int i = 2; i < values.Length; i++)
        {
            if (values[i] == Numbers.Prime)
                yield return i;
        }
    }

    int FirstUnset(Numbers[] values, int last)
    {
        for (int i = last; i < values.Length; i++)
            if (values[i] == Numbers.Unset)
                return i;

        return -1;
    }

    enum Numbers
    {
        Unset,
        Prime,
        Composite
    }

Answer 11

حقوق الطبع والنشر 2009 من قبل سانت Wittum 13189 برلين ألمانيا تحت CC-BY-SA https://creativecommons.org/licenses/by-sa/3.0/

بسيطة ولكنها أنيقة أكثر من طريقة لحساب كل يعبي سيكون هذا ، ولكن هذه الطريقة بطيئة و الذاكرة تكاليف أعلى بكثير عن أرقام أعلى لأن استخدام أعضاء هيئة التدريس (!) وظيفة ...ولكنه يدل على الاختلاف ويلسون Theoreme في تطبيق لتوليد جميع يعبي بواسطة خوارزمية نفذت في بايثون

#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
    if f%p%2:
        print p
    p+=1
    f*=(p-2)

Answer 12

باستخدام نفس الخوارزمية، يمكنك القيام بذلك بشكل أقصر قليلاً:

List<int> primes=new List<int>(new int[]{2,3});
for (int n = 5; primes.Count< numberToGenerate; n+=2)
{
  bool isPrime = true;
  foreach (int prime in primes)
  {
    if (n % prime == 0)
    {
      isPrime = false;
      break;
    }
  }
  if (isPrime)
    primes.Add(n);
}

Answer 13

لقد كتبت تطبيقًا بسيطًا لإراتوستينس في لغة C# باستخدام بعض LINQ.

لسوء الحظ، لا يوفر LINQ تسلسلاً لا نهائيًا من ints لذا يتعين عليك استخدام int.MaxValue:(

اضطررت إلى تخزين المرشح sqrt في نوع مجهول لتجنب حسابه لكل عدد أولي مخبأ (يبدو قبيحًا بعض الشيء).

أستخدم قائمة من الأعداد الأولية السابقة حتى sqrt للمرشح

cache.TakeWhile(c => c <= candidate.Sqrt)

وتحقق من كل Int بدءًا من 2 مقابله

.Any(cachedPrime => candidate.Current % cachedPrime == 0)

هنا هو الرمز:

static IEnumerable<int> Primes(int count)
{
    return Primes().Take(count);
}

static IEnumerable<int> Primes()
{
    List<int> cache = new List<int>();

    var primes = Enumerable.Range(2, int.MaxValue - 2).Select(candidate => new 
    {
        Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
        Current = candidate
    }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
            .Any(cachedPrime => candidate.Current % cachedPrime == 0))
            .Select(p => p.Current);

    foreach (var prime in primes)
    {
        cache.Add(prime);
        yield return prime;
    }
}

هناك تحسين آخر وهو تجنب التحقق من الأرقام الزوجية وإرجاع 2 فقط قبل إنشاء القائمة.بهذه الطريقة، إذا كانت طريقة الاستدعاء تطلب رقمًا أوليًا واحدًا فقط، فستتجنب كل الفوضى:

static IEnumerable<int> Primes()
{
    yield return 2;
    List<int> cache = new List<int>() { 2 };

    var primes = Enumerable.Range(3, int.MaxValue - 3)
        .Where(candidate => candidate % 2 != 0)
        .Select(candidate => new
    {
        Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
        Current = candidate
    }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
            .Any(cachedPrime => candidate.Current % cachedPrime == 0))
            .Select(p => p.Current);

    foreach (var prime in primes)
    {
        cache.Add(prime);
        yield return prime;
    }
}

Answer 14

لجعله أكثر أناقة، يجب عليك إعادة بناء اختبار IsPrime الخاص بك إلى طريقة منفصلة، ​​والتعامل مع التكرارات والزيادات خارج ذلك.

Answer 15

لقد فعلت ذلك في Java باستخدام مكتبة وظيفية كتبتها، ولكن بما أن مكتبتي تستخدم نفس المفاهيم مثل Enumerations، فأنا متأكد من أن الكود قابل للتكيف:

Iterable<Integer> numbers = new Range(1, 100);
Iterable<Integer> primes = numbers.inject(numbers, new Functions.Injecter<Iterable<Integer>, Integer>()
{
    public Iterable<Integer> call(Iterable<Integer> numbers, final Integer number) throws Exception
    {
        // We don't test for 1 which is implicit
        if ( number <= 1 )
        {
            return numbers;
        }
        // Only keep in numbers those that do not divide by number
        return numbers.reject(new Functions.Predicate1<Integer>()
        {
            public Boolean call(Integer n) throws Exception
            {
                return n > number && n % number == 0;
            }
        });
    }
});

Answer 16

فيما يلي مثال لكود بايثون الذي يطبع مجموع جميع الأعداد الأولية التي تقل عن مليونين:

from math import *

limit = 2000000
sievebound = (limit - 1) / 2
# sieve only odd numbers to save memory
# the ith element corresponds to the odd number 2*i+1
sieve = [False for n in xrange(1, sievebound + 1)]
crosslimit = (int(ceil(sqrt(limit))) - 1) / 2
for i in xrange(1, crosslimit):
    if not sieve[i]:
        # if p == 2*i + 1, then
        #   p**2 == 4*(i**2) + 4*i + 1
        #        == 2*i * (i + 1)
        for j in xrange(2*i * (i + 1), sievebound, 2*i + 1):
            sieve[j] = True
sum = 2
for i in xrange(1, sievebound):
    if not sieve[i]:
        sum = sum + (2*i+1)
print sum

Answer 17

هذا هو الأكثر أناقة الذي يمكنني التفكير فيه في وقت قصير.

ArrayList generatePrimes(int numberToGenerate)
{
    ArrayList rez = new ArrayList();

    rez.Add(2);
    rez.Add(3);

    for(int i = 5; rez.Count <= numberToGenerate; i+=2)
    {
        bool prime = true;
        for (int j = 2; j < Math.Sqrt(i); j++)
        {
            if (i % j == 0)
            {
                    prime = false;
                    break;
            }
        }
        if (prime) rez.Add(i);
    }

    return rez;
}

نأمل أن يساعد هذا على إعطائك فكرة.أنا متأكد من أنه يمكن تحسين هذا، ولكن من المفترض أن يعطيك فكرة عن كيفية جعل نسختك أكثر أناقة.

يحرر: كما هو مذكور في التعليقات، تقوم هذه الخوارزمية بالفعل بإرجاع قيم خاطئة لـ numberToGenerate < 2.أريد فقط أن أشير إلى أنني لم أكن أحاول أن أنشر له طريقة رائعة لتوليد الأعداد الأولية (انظر إلى إجابة هنري لذلك)، كنت أشير إلى كيفية جعل طريقته أكثر أناقة.

Answer 18

باستخدام البرمجة القائمة على الدفق في جافا الوظيفية, ، توصلت إلى ما يلي.نوع Natural هو في الأساس أ BigInteger >= 0.

public static Stream<Natural> sieve(final Stream<Natural> xs)
{ return cons(xs.head(), new P1<Stream<Natural>>()
  { public Stream<Natural> _1()
    { return sieve(xs.tail()._1()
                   .filter($(naturalOrd.equal().eq(ZERO))
                           .o(mod.f(xs.head())))); }}); }

public static final Stream<Natural> primes
  = sieve(forever(naturalEnumerator, natural(2).some()));

الآن لديك قيمة يمكنك حملها معك، وهي عبارة عن تدفق لا نهائي من الأعداد الأولية.يمكنك القيام بأشياء مثل هذا:

// Take the first n primes
Stream<Natural> nprimes = primes.take(n);

// Get the millionth prime
Natural mprime = primes.index(1000000);

// Get all primes less than n
Stream<Natural> pltn = primes.takeWhile(naturalOrd.lessThan(n));

شرح الغربال:

1. افترض أن الرقم الأول في دفق الوسيطة هو رقم أولي وضعه في مقدمة دفق العودة.أما باقي تدفق العودة فهو عبارة عن عملية حسابية يتم إنتاجها فقط عند الطلب.
2. إذا طلب شخص ما بقية الدفق، فاتصل بـ sieve على بقية دفق الوسيطة، وقم بتصفية الأرقام القابلة للقسمة على الرقم الأول (ما تبقى من القسمة هو صفر).

يجب أن يكون لديك الواردات التالية:

import fj.P1;
import static fj.FW.$;
import static fj.data.Enumerator.naturalEnumerator;
import fj.data.Natural;
import static fj.data.Natural.*;
import fj.data.Stream;
import static fj.data.Stream.*;
import static fj.pre.Ord.naturalOrd;

Answer 19

أنا شخصياً أعتقد أن هذا تطبيق قصير ونظيف (Java):

static ArrayList<Integer> getPrimes(int numPrimes) {
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    int n = 2;
    while (primes.size() < numPrimes) {
        while (!isPrime(n)) { n++; }
        primes.add(n);
        n++;
    }
    return primes;
}

static boolean isPrime(int n) {
    if (n < 2) { return false; }
    if (n == 2) { return true; }
    if (n % 2 == 0) { return false; }
    int d = 3;
    while (d * d <= n) {
        if (n % d == 0) { return false; }
        d += 2;
    }
    return true;
}

Answer 20

جرب استعلام LINQ هذا، فهو يولد أرقامًا أولية كما توقعت

        var NoOfPrimes= 5;
        var GeneratedPrime = Enumerable.Range(1, int.MaxValue)
          .Where(x =>
            {
                 return (x==1)? false:
                        !Enumerable.Range(1, (int)Math.Sqrt(x))
                        .Any(z => (x % z == 0 && x != z && z != 1));
            }).Select(no => no).TakeWhile((val, idx) => idx <= NoOfPrimes-1).ToList();

Answer 21

// Create a test range
IEnumerable<int> range = Enumerable.Range(3, 50 - 3);

// Sequential prime number generator
var primes_ = from n in range
     let w = (int)Math.Sqrt(n)
     where Enumerable.Range(2, w).All((i) => n % i > 0)
     select n;

// Note sequence of output:
// 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
foreach (var p in primes_)
    Trace.Write(p + ", ");
Trace.WriteLine("");

Answer 22

أبسط طريقة هي التجربة والخطأ:تحاول إذا كان أي رقم بين 2 و n-1 يقسم مرشحك الأولي n.
الاختصارات الأولى هي بالطبع أ) ما عليك سوى التحقق من الأرقام الفردية، و ب) ما عليك سوى التحقق من وجود فواصل تصل إلى sqrt(n).

في حالتك، حيث تقوم بإنشاء جميع الأعداد الأولية السابقة في العملية أيضًا، ما عليك سوى التحقق مما إذا كان أي من الأعداد الأولية في قائمتك، حتى sqrt(n)، يقسم n.
يجب أن يكون أسرع ما يمكنك الحصول عليه مقابل أموالك :-)

يحرر
طيب الكود انت طلبتهلكني أحذرك :-)، هذا كود دلفي سريع ومبهم لمدة 5 دقائق:

procedure TForm1.Button1Click(Sender: TObject);
const
  N = 100;
var
  PrimeList: TList;
  I, J, SqrtP: Integer;
  Divides: Boolean;
begin
  PrimeList := TList.Create;
  for I := 2 to N do begin
    SqrtP := Ceil(Sqrt(I));
    J := 0;
    Divides := False;
    while (not Divides) and (J < PrimeList.Count) 
                        and (Integer(PrimeList[J]) <= SqrtP) do begin
      Divides := ( I mod Integer(PrimeList[J]) = 0 );
      inc(J);
    end;
    if not Divides then
      PrimeList.Add(Pointer(I));
  end;
  // display results
  for I := 0 to PrimeList.Count - 1 do
    ListBox1.Items.Add(IntToStr(Integer(PrimeList[I])));
  PrimeList.Free;
end;

Answer 23

لمعرفة أول 100 عدد أولي، يمكن مراعاة اتباع كود جافا.

int num = 2;
int i, count;
int nPrimeCount = 0;
int primeCount = 0;

    do
    {

        for (i = 2; i <num; i++)
        {

             int n = num % i;

             if (n == 0) {

             nPrimeCount++;
         //  System.out.println(nPrimeCount + " " + "Non-Prime Number is: " + num);

             num++;
             break;

             }
       }

                if (i == num) {

                    primeCount++;

                    System.out.println(primeCount + " " + "Prime number is: " + num);
                    num++;
                }


     }while (primeCount<100);

Answer 24

لقد حصلت على هذا من خلال القراءة الأولى لـ "Sieve of Atkin" على Wikki بالإضافة إلى بعض الأفكار المسبقة التي قدمتها لهذا - أقضي الكثير من الوقت في البرمجة من الصفر وأركز تمامًا على الأشخاص الذين ينتقدون الترميز الكثيف للغاية الذي يشبه المترجم style + لم أقم حتى بمحاولة أولى لتشغيل الكود ...العديد من النماذج التي تعلمت استخدامها موجودة هنا، فقط اقرأ وابكي، احصل على ما تستطيع.

كن متأكدًا تمامًا من اختبار كل هذا قبل أي استخدام، وتأكد من عدم إظهاره لأي شخص - فهو مخصص للقراءة والنظر في الأفكار.أحتاج إلى تشغيل الأداة الأولية، لذا فإن هذا هو المكان الذي أبدأ فيه في كل مرة يتعين علي فيها تشغيل شيء ما.

احصل على ترجمة واحدة نظيفة، ثم ابدأ في إزالة ما هو معيب - لدي ما يقرب من 108 مليون ضغطة مفتاح من التعليمات البرمجية القابلة للاستخدام للقيام بذلك بهذه الطريقة، ...استخدم ما تستطيع.

سأعمل على نسختي غدا.

package demo;
// This code is a discussion of an opinion in a technical forum.
// It's use as a basis for further work is not prohibited.
import java.util.Arrays;
import java.util.HashSet;
import java.util.ArrayList;
import java.security.GeneralSecurityException;

/**
 * May we start by ignores any numbers divisible by two, three, or five
 * and eliminate from algorithm 3, 5, 7, 11, 13, 17, 19 completely - as
 * these may be done by hand. Then, with some thought we can completely
 * prove to certainty that no number larger than square-root the number
 * can possibly be a candidate prime.
 */

public class PrimeGenerator<T>
{
    //
    Integer HOW_MANY;
    HashSet<Integer>hashSet=new HashSet<Integer>();
    static final java.lang.String LINE_SEPARATOR
       =
       new java.lang.String(java.lang.System.getProperty("line.separator"));//
    //
    PrimeGenerator(Integer howMany) throws GeneralSecurityException
    {
        if(howMany.intValue() < 20)
        {
            throw new GeneralSecurityException("I'm insecure.");
        }
        else
        {
            this.HOW_MANY=howMany;
        }
    }
    // Let us then take from the rich literature readily 
    // available on primes and discount
    // time-wasters to the extent possible, utilizing the modulo operator to obtain some
    // faster operations.
    //
    // Numbers with modulo sixty remainder in these lists are known to be composite.
    //
    final HashSet<Integer> fillArray() throws GeneralSecurityException
    {
        // All numbers with modulo-sixty remainder in this list are not prime.
        int[]list1=new int[]{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,
        32,34,36,38,40,42,44,46,48,50,52,54,56,58};        //
        for(int nextInt:list1)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list1");//
            }
        }
        // All numbers with modulo-sixty remainder in this list are  are
        // divisible by three and not prime.
        int[]list2=new int[]{3,9,15,21,27,33,39,45,51,57};
        //
        for(int nextInt:list2)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list2");//
            }
        }
        // All numbers with modulo-sixty remainder in this list are
        // divisible by five and not prime. not prime.
        int[]list3=new int[]{5,25,35,55};
        //
        for(int nextInt:list3)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list3");//
            }
        }
        // All numbers with modulo-sixty remainder in
        // this list have a modulo-four remainder of 1.
        // What that means, I have neither clue nor guess - I got all this from
        int[]list4=new int[]{1,13,17,29,37,41,49,53};
        //
        for(int nextInt:list4)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list4");//
            }
        }
        Integer lowerBound=new Integer(19);// duh
        Double upperStartingPoint=new Double(Math.ceil(Math.sqrt(Integer.MAX_VALUE)));//
        int upperBound=upperStartingPoint.intValue();//
        HashSet<Integer> resultSet=new HashSet<Integer>();
        // use a loop.
        do
        {
            // One of those one liners, whole program here:
            int aModulo=upperBound % 60;
            if(this.hashSet.contains(new Integer(aModulo)))
            {
                continue;
            }
            else
            {
                resultSet.add(new Integer(aModulo));//
            }
        }
        while(--upperBound > 20);
        // this as an operator here is useful later in your work.
        return resultSet;
    }
    // Test harness ....
    public static void main(java.lang.String[] args)
    {
        return;
    }
}
//eof

Answer 25

جرب هذا الرمز.

protected bool isPrimeNubmer(int n)
    {
        if (n % 2 == 0)
            return false;
        else
        {
            int j = 3;
            int k = (n + 1) / 2 ;

            while (j <= k)
            {
                if (n % j == 0)
                    return false;
                j = j + 2;
            }
            return true;
        }
    }
    protected void btn_primeNumbers_Click(object sender, EventArgs e)
    {
        string time = "";
        lbl_message.Text = string.Empty;
        int num;

        StringBuilder builder = new StringBuilder();

        builder.Append("<table><tr>");
        if (int.TryParse(tb_number.Text, out num))
        {
            if (num < 0)
                lbl_message.Text = "Please enter a number greater than or equal to 0.";
            else
            {
                int count = 1;
                int number = 0;
                int cols = 11;

                var watch = Stopwatch.StartNew();

                while (count <= num)
                {
                    if (isPrimeNubmer(number))
                    {
                        if (cols > 0)
                        {
                            builder.Append("<td>" + count + " - " + number + "</td>");
                        }
                        else
                        {
                            builder.Append("</tr><tr><td>" + count + " - " + number + "</td>");
                            cols = 11;
                        }
                        count++;
                        number++;
                        cols--;
                    }
                    else
                        number++;
                }
                builder.Append("</table>");
                watch.Stop();
                var elapsedms = watch.ElapsedMilliseconds;
                double seconds = elapsedms / 1000;
                time = seconds.ToString();
                lbl_message.Text = builder.ToString();
                lbl_time.Text = time;
            }
        }
        else
            lbl_message.Text = "Please enter a numberic number.";

        lbl_time.Text = time;

        tb_number.Text = "";
        tb_number.Focus();
    }

هنا هو رمز aspx.

<form id="form1" runat="server">
    <div>
        <p>Please enter a number: <asp:TextBox ID="tb_number" runat="server"></asp:TextBox></p>

        <p><asp:Button ID="btn_primeNumbers" runat="server" Text="Show Prime Numbers" OnClick="btn_primeNumbers_Click" />
        </p>
        <p><asp:Label ID="lbl_time" runat="server"></asp:Label></p>
        <p><asp:Label ID="lbl_message" runat="server"></asp:Label></p>
    </div>
</form>

نتائج:10000 رقم أولي في أقل من ثانية واحدة

100000 عدد أولي في 63 ثانية

لقطة شاشة لأول 100 رقم أولي