Count Primes
الدرس 3 من 3 في دورة تحديات البرمجة للمقابلات - الحزمة الخامسة على Coddy.
التحدي
صعباكتب دالة countPrimes تستقبل عدداً صحيحاً n، وتعيد عدد الأعداد الأولية التي هي أقل من n.
ملاحظة: يجب أن يكون التعقيد الزمني أفضل من O(nlogn)
1 <= n <= 1000000
أمثلة:
الإدخال - 10
المخرجات المتوقعة - 4
الشرح - هناك 4 أعداد أولية أقل من 10 وهي: 2، 3، 5، 7
الإدخال - 13
المخرجات المتوقعة - 5
الشرح - هناك 5 أعداد أولية أقل من 13 وهي: 2، 3، 5، 7، 11 - لاحظ أن 13 لا يتم احتسابه!
جرّب بنفسك
int countPrimes(int n) {
// اكتب الكود هنا
}