24 ΠΔΠ - 1η Φάση: Λύσεις

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
bugos
Δημοσιεύσεις: 8
Εγγραφή: Κυρ Νοέμ 20, 2011 11:03 pm

24 ΠΔΠ - 1η Φάση: Λύσεις

Δημοσίευση από bugos »

Ορίστε η δικιά μου
http://pastebin.com/D5jzUPBe

Κώδικας: Επιλογή όλων

#include <stdio.h>
#include <cmath>

typedef unsigned short int   u_int16;
typedef unsigned       char  u_int8;

bool isPrime(u_int16 n) {
    u_int8 max = ceil(sqrt(n)); //check up to sqrt
    for(u_int16 i = 3; i <= max; i += 2) if (n % i == 0) return 0;
    return 1;
}

int main() {
    u_int16 x, y;
    FILE *in = fopen("function.in",  "r"),
        *out = fopen("function.out", "w");

    fscanf(in, "%5hu %5hu", &x, &y);

    if (x > y) {x = x ^ y; y = x ^ y; x = x ^ y;} //swap x,y
    x+=(x % 2 == 0)?1:2;//if (x % 2 == 0) x++;

    for(; x < y; x += 2) if (isPrime(x)) fprintf(out, "%u ", x);

    if (ftell(out)) { //if output not empty
        fseek(out, -1, SEEK_END);
        fprintf(out, "\n"); //replace last char with \n
    }

    fclose(in);
    fclose(out);
    return 0;
}
infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: 24 ΠΔΠ - 1η Φάση: Λύσεις

Δημοσίευση από infinity »

και η δική μου:
[pastebin]http://pastebin.com/vgpiuZkW[/pastebin]
Άβαταρ μέλους
mariosal
Δημοσιεύσεις: 63
Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
Τοποθεσία: Χολαργός, Ελλάδα
Επικοινωνία:

Re: 24 ΠΔΠ - 1η Φάση: Λύσεις

Δημοσίευση από mariosal »

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: 24 ΠΔΠ - 1η Φάση: Λύσεις

Δημοσίευση από Κηπουρίδης »

Για να ελέγξουμε αν ένας αριθμός είναι πρώτος, δεν είναι ανάγκη να ελέγξουμε
for ( i=2; i< num/2; ++i ) {
if ( num % i ) {
not_prime();
}
}

Μπορούμε να ελέγξουμε απλά μέχρι την τετραγωνική ρίζα του αριθμού
for ( i=2; i<= sqrt (num); ++i ) .......
Απόδειξη :
Αν ένας αριθμός δεν είναι πρώτος, τότε αναλύεται σε δύο άλλους αριθμούς ( εξ ορισμού ).
Αν και οι δύο ήταν μεγαλύτεροι από την τετραγωνική του ρίζα, τότε το γινόμενό τους θα ήταν μεγαλύτερο του αριθμού :? - καραάτοπο. Άρα σίγουρα ο μικρότερος από τους δύο θα είναι μικρότερος ή ίσος της τετραγωνικής ρίζας του ζητούμενου αριθμού.

Έτσι με μόνο αυτή τη βελτίωση, η πολυπλοκότητα του αλγορίθμου πέφτει από Ν^2 σε Ν*sqrt(N).

Όμως και πάλι, δεν είναι ανάγκη να ελέγχουμε με κάθε αριθμό στο διάστημα [2,sqrt(N)] αλλά μόνο με τους πρώτους αριθμούς εδώ μέσα ( ο μικρός αριθμός για τον οποίο μιλήσαμε πιο πάνω ή πρώτος είναι, ή αν δεν είναι, αναλύεται σε πρώτους ( πάλι εξ`ορισμού ), άρα αν κάποιος αριθμός σε αυτό το διάστημα διαιρεί τον ζητούμενό μας σε, τότε σίγουρα κάποιος πρώτος τον διαιρεί ). Επομένως μια ακόμα μικρή βελτίωση θα είναι να προϋπολογίσουμε όλους τους πρώτους μέχρι τη ρίζα του maxN και μετά να ελέγχουμε κάθε φορά με αυτούς ( μέχρι κάποιος από αυτούς να ξεπεράσει την τετραγωνική ρίζα του ζητούμενου αριθμού μας για την ακρίβεια ).

Τελευταία βελτίωση, τους πρώτους αριθμούς μέχρι την τετραγωνική ρίζα του maxN, τους βρίσκουμε με κόσκινο του ερατοσθένη.

Πιο γρήγορη λύση, δεν ξέρω.

Υ.Γ.: Σε τεστ που έκανα στον υπολογιστή μου, να τρέχεις έναν έναν όλους τους αριθμούς μέχρι την ρίζα του ζητούμενου είναι κατά ελάχιστα πιο αργό ( τόσο ελάχιστο που δεν αξίζει να αλλάξεις αλγόριθμο σε διαγωνισμό ) από το κόσκινο του Ερατοσθένη, κι η μέθοδος που περιγράφω πιο πάνω ελάχιστα πιο γρήγορη από αυτές τις δύο, άρα πιο πολύ θεωρητικό ενδιαφέρον έχει, παρά πρακτικό.
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: 24 ΠΔΠ - 1η Φάση: Λύσεις

Δημοσίευση από infinity »

Κηπουρίδης έγραψε:Για να ελέγξουμε αν ένας αριθμός είναι πρώτος, δεν είναι ανάγκη να ελέγξουμε
for ( i=2; i< num/2; ++i ) {
if ( num % i ) {
not_prime();
}
}

Μπορούμε να ελέγξουμε απλά μέχρι την τετραγωνική ρίζα του αριθμού
for ( i=2; i<= sqrt (num); ++i ) .......
Απόδειξη :
Αν ένας αριθμός δεν είναι πρώτος, τότε αναλύεται σε δύο άλλους αριθμούς ( εξ ορισμού ).
Αν και οι δύο ήταν μεγαλύτεροι από την τετραγωνική του ρίζα, τότε το γινόμενό τους θα ήταν μεγαλύτερο του αριθμού :? - καραάτοπο. Άρα σίγουρα ο μικρότερος από τους δύο θα είναι μικρότερος ή ίσος της τετραγωνικής ρίζας του ζητούμενου αριθμού.

Έτσι με μόνο αυτή τη βελτίωση, η πολυπλοκότητα του αλγορίθμου πέφτει από Ν^2 σε Ν*sqrt(N).

Όμως και πάλι, δεν είναι ανάγκη να ελέγχουμε με κάθε αριθμό στο διάστημα [2,sqrt(N)] αλλά μόνο με τους πρώτους αριθμούς εδώ μέσα ( ο μικρός αριθμός για τον οποίο μιλήσαμε πιο πάνω ή πρώτος είναι, ή αν δεν είναι, αναλύεται σε πρώτους ( πάλι εξ`ορισμού ), άρα αν κάποιος αριθμός σε αυτό το διάστημα διαιρεί τον ζητούμενό μας σε, τότε σίγουρα κάποιος πρώτος τον διαιρεί ). Επομένως μια ακόμα μικρή βελτίωση θα είναι να προϋπολογίσουμε όλους τους πρώτους μέχρι τη ρίζα του maxN και μετά να ελέγχουμε κάθε φορά με αυτούς ( μέχρι κάποιος από αυτούς να ξεπεράσει την τετραγωνική ρίζα του ζητούμενου αριθμού μας για την ακρίβεια ).

Τελευταία βελτίωση, τους πρώτους αριθμούς μέχρι την τετραγωνική ρίζα του maxN, τους βρίσκουμε με κόσκινο του ερατοσθένη.

Πιο γρήγορη λύση, δεν ξέρω.

Υ.Γ.: Σε τεστ που έκανα στον υπολογιστή μου, να τρέχεις έναν έναν όλους τους αριθμούς μέχρι την ρίζα του ζητούμενου είναι κατά ελάχιστα πιο αργό ( τόσο ελάχιστο που δεν αξίζει να αλλάξεις αλγόριθμο σε διαγωνισμό ) από το κόσκινο του Ερατοσθένη, κι η μέθοδος που περιγράφω πιο πάνω ελάχιστα πιο γρήγορη από αυτές τις δύο, άρα πιο πολύ θεωρητικό ενδιαφέρον έχει, παρά πρακτικό.
Τα περισσότερα απ' όσα ανέφερες τα παρατήρησα λίγες μέρες πριν το πέρας των υποβολών, επειδή ήταν και η πρώτη φορα που λαμβάνω μέρος είπα να μην το διακινδυνέψω εφ' όσον είχα υλοποιήσει αυτό και τα όρια ήταν πολύ μικρά (δεν υπήρχε δηλαδή πιθανότητα να βγω εκτός ορίων χρόνου).Ευχαριστώ πάντως για τις συμβουλές :P
bugos
Δημοσιεύσεις: 8
Εγγραφή: Κυρ Νοέμ 20, 2011 11:03 pm

Re: 24 ΠΔΠ - 1η Φάση: Λύσεις

Δημοσίευση από bugos »

Ξανά η δικιά μου λύση (νεότερη έκδοση)
[pastebin]http://pastebin.com/7BtptEu8[/pastebin]

Προσπάθησα να χρησιμοποιήσω και το ότι κα΄θε πρώτος είναι της μορφής 6k+-1 αλλά μου δημιούργησε προβλήματα.
Άβαταρ μέλους
mariosal
Δημοσιεύσεις: 63
Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
Τοποθεσία: Χολαργός, Ελλάδα
Επικοινωνία:

Re: 24 ΠΔΠ - 1η Φάση: Λύσεις

Δημοσίευση από mariosal »

bugos έγραψε:κα΄θε πρώτος είναι της μορφής 6k+-1
Citation needed.
bugos
Δημοσιεύσεις: 8
Εγγραφή: Κυρ Νοέμ 20, 2011 11:03 pm

Re: 24 ΠΔΠ - 1η Φάση: Λύσεις

Δημοσίευση από bugos »

mariosal έγραψε:
bugos έγραψε:κα΄θε πρώτος είναι της μορφής 6k+-1
Citation needed.
http://en.wikipedia.org/wiki/Primality_test
... It can be improved further by observing that all primes are of the form 6k ± 1, with 2 and 3 being the only exceptions. This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3).
kostantinaras
Δημοσιεύσεις: 14
Εγγραφή: Πέμ Μαρ 08, 2012 3:40 pm

Re: 24 ΠΔΠ - 1η Φάση: Λύσεις

Δημοσίευση από kostantinaras »

Και η δικιά μου:
[pastebin]http://pastebin.com/GCYSk4SF[/pastebin]
In a world without walls and fenches who needs Windows and Gates?
Απάντηση