فقط حول الأعداد الأولية (طريقة تدريجية سريعة لحساب الأعداد الأولية)

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

الكود الأول:

public HashMap<Long, Long> serialPrimes() {
   long range = Long.parseLong(this.range.getText().toString());
   HashMap<Long, Long> primes = new HashMap<>(); //    
   HashMap<Long, ArrayList<Long>> spectres = new HashMap<>(); //     
   HashMap<Long, ArrayList<Long>> toppings = new HashMap<>(); //      
   for(long i = 2; i < range; i++){
       if(toppings.keySet().contains(i)) { //      ,     i
           //  
           ArrayList<Long> spectre = toppings.get(i);
           spectres.put(i, spectre);
           toppings.remove(i);
           for(long spectreValue : spectre) {
               //      
               long topping = primes.get(spectreValue) + spectreValue;
               primes.put(spectreValue, topping);
               //    
               if(toppings.keySet().contains(topping)) {
                   toppings.get(topping).add(spectreValue);
               } else {
                   ArrayList<Long> newSpectre = new ArrayList<>();
                   newSpectre.add(spectreValue);
                   toppings.put(topping, newSpectre);
               }
           }
       } else { //      ,     i
           //   
           primes.put(i, i + i); //       ,   
   //   
           //     
           ArrayList<Long> newSpectre = new ArrayList<>();
           newSpectre.add(i);
           toppings.put(i + i, newSpectre);
       }
   }
   return primes;
}

الآن شرح.

, .

API P2P .

, -.

3 :

:

• , 2 ()
• T
• ,
• 2*n (, 2[4])
• 4[2]
• ,
• ( , )

, .

1.500.000. , 2 . -, 3.000.000. 96 , 14 ( , ).

في المدى من 2 إلى 3.000.000 تقع 216.816 بدائية.

مثال Android

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