6

تحدي برمجي[011][سهل] الأعداد الأولية بين n و m

afaki
المزيد

هذه المرة التحدي سهل وواضح جدا لديك عددان n و m عليك ان تخرج عدد الأعداد الأولية بينهما (يشمل كلا العددين)

المدخلات

عددان n و m حيث

0 <= n, m <= 1000000
n < m

أمثلة

مثال #1

الإدخال

1 10

المخرجات

4

الأعداد الأولية بين 1 و 10 هي: 2, 3, 5, 7

مثال #2

المدخلات

50 200

المخرجات

31

الأعداد الأولية بين 50 و 200 هي 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199

مثال #3

المدخلات

1999 99999

المخرجات

9290

يجب أن يُنفذ البرنامج في أقل من ثانيتين

النسخة الصعبة

إذا وجدت هذا التحدي سهل جدا فجرب النسخة الصعبة

في هذه النسخة لديك عدة test cases بدلا من واحدة

المدخلات

أول سطر يحتوي على عدد t (أقصى قيمة ل t هي 300) بعدها يأتي عدد t سطر كل منهم يحتوي على n و m

مثال

6
1 10
2 4
100 300
700 1200
50 51
99 999

المخرجات

4
2
37
71
0
143

في هذه الحالة ال time limit خمس ثواني

يرجى الدخول لحسابك أو تسجيل حساب لتستطيع إضافة تعليق
حساب جديد دخول

التعليقات

3
zakariamouhid

إذا كانت الدقة غير مطلوبة يمكن استخدام أحد تقريبات الدالة

وإلا يمكن استخدام طريقة الغربال

حساب المدة بالنسبة للتحدي الصعب

/1

2
3mmarg97 
import java.util.Scanner;

public class Main {

public static boolean isPrime(int n) {
    if (n ==1)
        return false;
    for(int i=2;i*i <= n;i++) {
        if(n%i==0)
            return false;
    }
    return true;
}
public static void main(String[] args) {
    Scanner input = new Scanner(System.in);

    int n = input.nextInt();
    int m = input.nextInt();
    int counter = 0;

    for (int i = n; i < m; i++) {
        if (isPrime(i))
            counter++;
    }
    System.out.println(counter);
}
}

مدة تنفيذ أسوأ حالة :

0 1000000

هي 358 ms

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

0
afaki

البرنامج لا يعطي نتيجة صحيحة عندما يكون m عدد أولي

استبدل

for (int i = n; i < m; i++)

ب

for (int i = n; i <= m; i++)

بالنسبة للنسخة الصعبة لست متأكد إن كان يعمل في ال time limit

هل يمكنك مشاركة الكود للنسخة الصعبة؟

ثم جرب هذه ال testcase

0
3mmarg97

تجاوزت ال 10 ثواني على هذه ال testcase لم اتوقع أن يكون عدد الاسطر كبيرا لهذه الدرجة ، غالبا اذا بدلت طريقة القراءة من المستخدم مع بعض التعديلات على طريقة التحقق من العدد الاولي ستنجح ، سأجربها في المساء ان شاء الله

0
afaki

سأنشر الحل لاحقا إذا لم يتوصل إليه احد

2
محمد عزيز الكناني

solution to 1

 $ cat easy1.c
 #include <math.h>
 #include <stdlib.h>
 #include <stdio.h>

 char sieve[2 << 24] = {0};

 int main(int argc, char *argv[])
 {
         long long n, m;
         scanf("%Ld %Ld", &n, &m);
         long max = (long ) sqrt( (double)  m);
         long long i, f;
         for (i = 2; i <= max; i++) {
                 if ( !sieve[i] ) {
                         for (f = i*i; f <= m; f+=i) {
                                 sieve[f] = 1;
                         }
                 }
         }
         long long nb = 0;
         n = (n <= 2 ) ? 2 : n;
         for (i = n; i <= m; i++) {
                 if ( !sieve[i] ) nb++;
         }
         printf("%Ld\n", nb);
         return 0;
 }

solution to problem2

$ cat easy2.c

#include <math.h>
#include <stdlib.h>
#include <stdio.h>

char sieve[2 << 24] = {0};
long long ns[300];
long long ms[300];


int main(int argc, char *argv[])
{
        long long n, m, TC;
        scanf("%Ld", &TC);
        long long mmax = 0, nmin = 2<<24;
        int z = 0;
        while (TC--) {
                scanf("%Ld %Ld", &n, &m);
                if (m > mmax) mmax = m;
                if (n < nmin) nmin = n;
                ns[z] = n;
                ms[z] = m;
                z ++;
        }
        m = mmax;
        n = nmin;
        long max = (long ) sqrt( (double)  m);
        long long i, f;

        for (i = 2; i <= max; i++) {
                if ( !sieve[i] ) {
                        for (f = i*i; f <= m; f+=i) {
                                sieve[f] = 1;
                        }
                }
        }
        int k;
        long long nb;
        for (k = 0; k < z; k++) {
                nb = 0;
                ns[k] = (ns[k] <= 2 ) ? 2 : ns[k];
                for (i = ns[k]; i <= ms[k]; i++) {
                        if ( !sieve[i] ) nb++;
                }
                printf("%Ld\n", nb);
        }

        return 0;
}

كما أنه لديك خطأ في المثال الأخير المخرج 4 وليس 5

0
محمد عزيز الكناني

على جهازي تقريباً 30ms للمثال الأخير، و-2720 كب 

mo@mostation on Fri Jul 07 at 08:12 PM
~/code
$ gcc -O3 -lm easy2.c && /usr/bin/time -v ./a.out > /dev/null < in.txt
Command being timed: "./a.out"
User time (seconds): 0.03
System time (seconds): 0.00
Percent of CPU this job got: 97%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.03
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 2720
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 322
Voluntary context switches: 1
Involuntary context switches: 2
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
0
hanymoh

هذا الكود كتب بلغة روبى Ruby

def isPrime?(num)
  return false if num <= 1
  Math.sqrt(num).to_i.downto(2).each {|i| return false if num % i == 0}
  return true
end

count = 0    
prime_numbers = []
(1..10).step(1) do |num|
  prime = isPrime? num 
  if prime
    prime_numbers << num
    count += 1
  end
end

puts "counts is: #{count}"
puts prime_numbers
0
afaki

من المفترض ان تأخذ قيمة n و m من المستخدم

ايضا جرب النسخة الصعبة


اقرأ أيضًا