Πρόγραμμα: leia.c (25 μονάδες)
Γράψτε ένα πρόγραμμα που παίρνει ένα εύρος θετικών ακεραίων ως ορίσματα από την κονσόλα (το εύρος είναι κλειστό, δηλαδή περιέχει τα όρια) και τυπώνει πόσα ζεύγη δίδυμων πρώτων (twin primes) υπάρχουν σε αυτό το διάστημα. Ένα ζεύγος ακεραίων (n, n+2) είναι δίδυμοι πρώτοι αν και ο n και ο n+2 είναι πρώτοι. Για παράδειγμα, στο διάστημα [1, 10] υπάρχουν μόλις δύο ζεύγη δίδυμων πρώτων (3, 5) και (5, 7). Παραδείγματα εκτέλεσης ακολουθούν:
$ gcc -o leia leia.c
$ ./leia 1 10
2
$ ./leia 10 100
6
$ ./leia 1 10000000
58980
$ ./leia 100000000000 100000100000
182
Ένας έλεγχος πρώτου με δοκιμαστική διαίρεση για κάθε αριθμό του [1, 10^7] είναι αργός· το κόσκινο του Ερατοσθένη σε δυναμικά δεσμευμένο πίνακα είναι η κλασική λύση. Για διαστήματα όπως το [10^11, 10^11 + 10^5] δεν χωράει κόσκινο μέχρι το πάνω όριο: σκεφτείτε ένα «τμηματικό» κόσκινο, που χρησιμοποιεί τους πρώτους μέχρι τη ρίζα του πάνω ορίου για να σημαδέψει μόνο το ζητούμενο διάστημα. Προσέξτε ότι και τα δύο μέλη του ζεύγους πρέπει να είναι μέσα στο διάστημα και ότι οι αριθμοί θέλουν 64 bits.
Αριθμός στον οδηγό: Α15.18
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2023-fall-ex7-q3 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2023-fall-ex7-q3.html ·
Markdown (GitHub)