اعداد اول را خروجی بدهید

بازگشت به درس

یک عدد صحیح بزرگ تر از 1 زمانی اول صدا زده می شود که نتوان آن را به هر چیزی بدون اینکه باقی مانده داشته باشد تقسیم کرد به جز 1 و خودش.

به عبارتی دیگر، n > 1 یک عدد اول است اگر نتواند با هیچ چیزی به جز 1 و n به صورت مساوی تقسیم شود.

برای مثال، 5 یک عدد اول است، چون نمی تواند بدون باقی مانده به 2، 3 و 4 تقسیم شود.

کدی بنویسید که اعداد اول را در بازه 2 تا n خروجی بدهد

برای n = 10 نتیجه 7 ،5 ،3 ،2 خواهد بود.

ضمیمه: کد باید برای هر مقدار n کار کند، نه اینکه برای مقدار مشخصی تنظیم شده باشد.

There are many algorithms for this task.

Let’s use a nested loop:

          For each i in the interval {
  check if i has a divisor from 1..i
  if yes => the value is not a prime
  if no => the value is a prime, show it
}
        

The code using a label:

let n = 10;

nextPrime:
for (let i = 2; i <= n; i++) { // for each i...

  for (let j = 2; j < i; j++) { // look for a divisor..
    if (i % j == 0) continue nextPrime; // not a prime, go next i
  }

  alert( i ); // a prime
}

There’s a lot of space to optimize it. For instance, we could look for the divisors from 2 to square root of i. But anyway, if we want to be really efficient for large intervals, we need to change the approach and rely on advanced maths and complex algorithms like Quadratic sieve, General number field sieve etc.