Γενικό thread αποριών για τη C#.

[M2000]

Μπα δεν το κόβω ότι κάνει Ερατοσθένη...και να σου πω την αλήθεια υπάρχει τρόπος ακόμα και αν δεν κατανοείς το κώδικα επαρκώς να ξέρεις ότι είναι μούφα...Η χρήση του 2 τρεις φορές...είναι πλεονασμός...Η μία στο τέλος είναι για να τυπώσεις αλλά δυο για να κάνεις τη δουλειά είναι πολλά!

Και ο κώδικας του Amstrand  είναι σαφώς καλύτερος..και δεν έχει τρεις φορές το 2...

 

10 DEFINT a-z
20 INPUT "Limit";limit
30 DIM f(limit)
40 FOR n=2 TO SQR(limit)
50 IF f(n)=1 THEN 90
60 FOR k=n*n TO limit STEP n
70 f(k)=1
80 NEXT k
90 NEXT n
100 FOR n=2 TO limit
110 IF f(n)=0 THEN PRINT n;",";
120 NEXT

[Alithinos]

 

Even better

 

        static bool isPrime(int x)
        {
            for (var y = 2; y <= Math.Sqrt(x); y++)
            {
                if (x % y == 0)
                {
                     return false;
                }
            }

            return true;
        }

Simple is good.

 

 

Not as simple αλλά για να μπαίνεις στο κλίμα του LINQ

 

Func<int, bool> isPrime = x => Enumerable.Range(2, (int)(Math.Sqrt(x)) - 1)
                                         .All(y => x % y != 0);

var inputs = new[] { 2, 3, 4, 25, 31 };

foreach (var x in inputs)
{
    Console.WriteLine("{0} is {1}", x, isPrime(x) ? "prime" : "not prime");
}

 

Το πρώτο μ' άρεσε. Δεν ξόδεψα αρκετό χρόνο για να αντιληφθώ ότι η bool μέσα στη συνάρτηση bool δεν χρειάζεται πλέον.

Στο δεύτερο παράδειγμα όμως με το LINQ με έχασες!

 

Μόνο αυτό το κομμάτι κατάλαβα τι κάνει:

var inputs = new[] { 2, 3, 4, 25, 31 };

foreach (var x in inputs)
{
    Console.WriteLine("{0} is {1}", x, isPrime(x) ? "prime" : "not prime");
}

Το LINQ θα αρχίσω να το μαθαίνω αργότερα.

Έχω ένα βιβλίο το οποίο διαβάζω με τη σειρά, και μόλις τελείωσα το κεφάλαιο 4, και το LINQ είναι στο 14.

http://www.mgiurdas.gr/sites/default/files/toc/20-5776-bookcontents.pdf

 

Υ.Γ. Έχω και το Programming C# 5.0, το οποίο καλύπτει όλα αυτά, και επιπλέον τα χαρακτηριστικά που προσθέτουν η 4.0 και η 5.0 έκδοση, και ακόμα πως χρησιμοποιείται η C# με XAML, ASP... αλλά το χω αφήσει στην άκρη για να το διαβάσω για τα επιπρόσθετα θέματα που καλύπτει αφού τελειώσω πρώτα τον 'Οδηγό' , γιατί ο Οδηγός έχει στο τέλος κάθε κεφαλαίου και ασκήσεις, ερωτήσεις κτλπ.

Alithinos,

Tο πρόγραμμα έχει ένα θέμα! Παρατηρούμε ότι εκτελείς διαιρέσεις (ελέγχεις το υπόλοιπο). Ενώ η λύση δεν θέλει διαίρεση!

Ασφαλώς και το Simple είναι Good...αλλά όταν υπάρχει: Ερατοσθένης και Euler, δεν μπορούμε να τους αγνοούμε. Και εδώ μιλάμε για απλότητα!

Ξεκινάς από το 2 και βγάζεις εκτός (με έναν τρόπο) όλα τα νούμερα μέχρι το 100 με βήμα 2, μετά πας στο 3 και βγάζεις εκτός όλα τα νούμερα μέχρι το 100 με βήμα 3...και συνεχίζεις μέχρι  το τετράγωνο του αριθμού, που βάζεις κάθε φορά για βήμα να πάει πάνω από το 100. Πάντα επιλέγεις για βήμα έναν αριθμό που δεν έχει βγει εκτός. Εκτός βγαίνουν οι αριθμοί με αφαίρεση. Ξεκινούν από το μηδέν και όποιος είναι <0 είναι εκτός. Στο τέλος όσοι αριθμοί (θέσεις στο πίνακα) είναι 0 τότε είναι πρώτος.

 

Έτσι όπως το λες, έχει θέμα. Και έχει θέμα γιατί η λύση που μου προτείνεις τοποθετεί τις τιμές σε ένα πίνακα, και επεξεργάζεται τα δεδομένα του πίνακα.

 

Και όπως είχα γράψει σε προηγούμενη απάντηση δεν έχω καλύψει ακόμα τις δομές δεδομένων και τους αλγόριθμους επεξεργασίας τους.

 

Για αυτό δεν χρησιμοποίησα αυτούς τους αλγόριθμους. 

 

Θα είναι το επόμενο που θα αρχίσω να μαθαίνω, αφού κάνω μια επανάληψη και παραπάνω εξάσκηση στα όσα έχω ήδη καλύψει.

[defacer]

Το πρώτο μ' άρεσε. Δεν ξόδεψα αρκετό χρόνο για να αντιληφθώ ότι η bool μέσα στη συνάρτηση bool δεν χρειάζεται πλέον.

Στο δεύτερο παράδειγμα όμως με το LINQ με έχασες!

 

Η δομή του πρώτου είναι το κλασικό στυλ που γράφεις ένα φίλτρο της κατηγορίας "any" ή "some" ή "all" (διαφορετικές γλώσσες προτιμούν διαφορετικό όνομα) με κάποιο predicate (το οποίο εδώ είναι η συνθήκη του if). Αν συνεχίσεις να προγραμματίζεις θα το συναντάς κάθε τόσο.

 

Το δεύτερο απλά το έγραψα τώρα που γυρίζει. Άστο και έλα να το ξαναδείς όταν θα είναι η ώρα του.

Μπα δεν το κόβω ότι κάνει Ερατοσθένη...και να σου πω την αλήθεια υπάρχει τρόπος ακόμα και αν δεν κατανοείς το κώδικα επαρκώς να ξέρεις ότι είναι μούφα...Η χρήση του 2 τρεις φορές...είναι πλεονασμός...Η μία στο τέλος είναι για να τυπώσεις αλλά δυο για να κάνεις τη δουλειά είναι πολλά!

Και ο κώδικας του Amstrand  είναι σαφώς καλύτερος..και δεν έχει τρεις φορές το 2...

 

Επίτηδες να το έκανες για να γίνεις ρόμπα δε θα μπορούσες να τα καταφέρεις καλύτερα.

[groot]

Επίτηδες να το έκανες για να γίνεις ρόμπα δε θα μπορούσες να τα καταφέρεις καλύτερα.

Μέχρι να μάθεις να μην γράφεις 3 φορές 2, θα διαβάζεις αυτό το μήνυμα του Μ2000. Δηλαδή, εάν την άλλη φορά χρειαστείς το 6, τι θα γίνει; Θα μας πάρει ο διάολος; Καλά τα λέει ο Μ2000.

 

 

Και του χρόνου.

[defacer]

Groot άσε μας. Μπορεί να μη κατανοώ τι γράφεις επαρκώς αλλά ξέρω ότι είναι μούφα.

[Kercyn]

Func<int, IEnumerable<int>> nonPrimesUpTo = limit => 
    Enumerable.Range(2, (int)(Math.Sqrt(limit)) - 1)
              .SelectMany(x => Enumerable.Range(2, limit / x).Select(y => x * y))
              .Distinct();

Func<int, IEnumerable<int>> sieve = limit => Enumerable.Range(2, limit - 1)
                                                       .Except(nonPrimesUpTo(limit));

foreach (var prime in sieve(100))
{
    Console.WriteLine(prime);
}

 

Ρε συ defacer για βοήθα λίγο μ' αυτό το ματζαφλάρι που έγραψες.

Το nonPrimesUpTo είναι ένα function που παίρνει int (την οποία ονομάζεις limit) και επιστρέφει IEnumerable<int>.

Από 2 μέχρι ((int)(ρίζα limit) - 1), διαλέγει όλους τους ξεχωριστούς αριθμούς x οι οποίοι:

Είναι από 2 μέχρι limit/x και ικανοποιούν τι; Τι κάνει το δεύτερο select με το y;

 

Μετά, το sieve είναι όλοι οι αριθμοί από 2 μέχρι limit - 1 εκτός απ' αυτούς που επιστρέφονται από την nonPrimesUpTo για limit.

[defacer]

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

 

Το να βρεις τους μη-πρώτους είναι στην ουσία το real work βήμα του sieve. Πώς θα βρεις όλους τους μη-πρώτους; Sieve style. Θα πάρεις τα νούμερα από το 2 μέχρι και το sqrt(limit). Έστω x το κάθε ένα από αυτά τα νούμερα.

 

Με δεδομένο το x πρέπει τώρα να βρεις όλα του τα πολλαπλάσια p που είναι p <= limit, να τα μαζέψεις όλα για κάθε x και να καταλήξεις έτσι στη λίστα με όλους τους μη-πρώτους <= limit. Με άλλα λόγια, θέλεις σαν αποτέλεσμα ένα enumerable που θα έχει μέσα όλα τα πολλαπλάσια του 2, και μετά όλα του 3, και μετά όλα του 4, κλπ μέχρι το sqrt(limit) (και εδώ κολλάει ότι το Distinct() δεν αλλάζει τη συμπεριφορά: όσες φορές και να μου πεις ότι το 8 δεν είναι πρώτος, δε θα αλλάξει κάτι).

 

Εδώ τώρα μια παρένθεση για τη SelectMany. Τι κάνει αυτή: παίρνει ένα enumerable sequence IN, κάνει project κάθε μία τιμή του σε ένα άλλο enumerable sequence OUT, και επιστρέφει ένα τρίτο enumerable sequence το οποίο είναι στην ουσία όλα τα OUT κολλημένα το ένα πίσω από το άλλο. Μπερδευτικό; Σκέψου το σαν SQL join. Παίρνεις ένα recordset, για κάθε ένα από τα rows του κάνεις join για να προκύψει ένα άλλο recordset, και το αποτέλεσμα της πράξης είναι όλα αυτά τα άλλα recordset κολλημένα μεταξύ τους.

 

Θέλω λοιπόν τα πολλαπλάσια του κάθε x που είναι <= limit. Αλλά για να το κάνω αυτό πρέπει να πολλαπλασιάσω. Με τι ακριβώς όμως θα πολλαπλασιάσω το x;

 

Εδώ έρχεται η SelectMany. Για κάθε x θα υπολογίσω το enumerable των πολλαπλαστιαστών του y, από αυτό θα κάνω select x * y για να υπολογίσω τα ίδια τα πολλαπλάσια p, και τέλος θα κολλήσω όλα τα enumerable των p μεταξύ τους.

 

Πώς θα υπολογίσω τα πολλαπλάσια του ενός x? Φυσικά θα πάρω ένα Enumerable.Sequence(...).Select(y => x * y) όπου y ο πολλαπλασιαστής κάθε φορά. Αυτό θα μπορούσα να το κάνω ως εξής

Enumerable.Sequence(2, int.MaxValue).Select(y => x * y).TakeWhile(p => p <= limit)

(int.MaxValue επειδή δεν ξέρω μέχρι πού θέλω να φτάσω με τους πολλαπλασιαστές, αλλά ξέρω σίγουρα ότι δε χρειάζεται να φτάσω μέχρι εκεί οπότε καλύφθηκα -- θα μπορούσε να μπει το limit εκεί εφόσον x >= 2 από πριν άρα όταν το y πάρει την limit-th τιμή του που είναι συγκεκριμένα limit + 1 τότε θα έχω p = x * y >= 2 * (limit + 1) > limit για κάθε limit, άρα θα ρίξει πόρτα η TakeWhile νωρίτερα άρα είμαι εντάξει)

 

Update: τελικά η σωστή τιμή για το count του Enumerable.Sequence εδώ είναι ακριβώς limit - 1 όπως προκύπτει από τα μαθηματικά παραπάνω και τη διαπίστωση του AllCowsEatGrass σε παρακάτω post.

 

Επειδή όμως όταν έγραφα το προηγούμενο δε σκέφτηκα την TakeWhile ¯\_(ツ)_/¯  πήγα με την άλλη μέθοδο: αφού p = x * y και θέλω p <= limit τότε προφανώς y <= limit / x. Οπότε,

 

Enumerable.Sequence(2, limit / x) // δίνει το σύνολο όλων των πολ/στών y για τους οποίους y >= 2 και x * y <= limit

    .Select(y => x * y) // κάνει τον πολλαπλασιασμό για να βρεί όλα τα πολλαπλάσια p του x για τα οποία p <= limit

 

Τέλος παίρνουμε οοοοοοοοοοοολα αυτά τα πολλαπλάσια και τα βάζουμε σε ένα hashtable με τη Distinct(), και μετά φιλτράρουμε τους ακεραίους ελέγχοντας αν είναι στο hashtable. Αυτό το βήμα προφανώς θα μπορούσε να γίνει και με άλλο data structure, όρεξη να υπάρχει.

 

Το χεις;

 

------

ΥΓ "but why?"

 

Eπειδή είναι functional, οπότε α) μαθαίνεις να σκέφτεσαι και functional αντί για imperative και β) ως functional είναι trivially parallelizable. Στην προκειμενη περίπτωση που κύριε πρέσβη μας κακομαθαίνετε με το PLINQ, πατάς ένα .AsParallel() και more or less συγχαρητήρια από single core το πρόγραμμα τώρα τρέχει παράλληλα σε όλες τις CPU.

Επεξ/σία 3 Απριλίου 2016 από defacer

[groot]

Groot άσε μας. Μπορεί να μη κατανοώ τι γράφεις επαρκώς αλλά ξέρω ότι είναι μούφα.

Εάν όντως πήρες πάσα και έπαιξες, καλό. Εάν όχι, well... ελπίζω το "ναι".

[Kercyn]

Τόσην ώρα το διαβάζω και προσπαθώ να καταλάβω και με το refresh βλέπω "έκανα πολλά edits". Η αλήθεια είναι πως δεν το πολυέχω τώρα, αλλά θα το κοιτάξω καλύτερα αύριο που θα είμαι και πιο ξεκούραστος και άμα έχω κάποια συγκεκριμένη απορία θα ξαναρωτήσω. Με LINQ έχω ασχοληθεί ελάχιστα (και τις περισσότερες φορές το χρησιμοποιούσα για να κάνω iterate σε containers AsList για να μπορώ να πειράζω τα πράγματα που είχαν μέσα), αλλά ό,τι μαθαίνει κανείς καλό είναι, και λέω να ξεκινήσω να μαθαίνω και C# λίγο καλύτερα.

 

Ευχαριστώ!

[παπι]

Τόσην ώρα το διαβάζω και προσπαθώ να καταλάβω και με το refresh βλέπω "έκανα πολλά edits". Η αλήθεια είναι πως δεν το πολυέχω τώρα, αλλά θα το κοιτάξω καλύτερα αύριο που θα είμαι και πιο ξεκούραστος και άμα έχω κάποια συγκεκριμένη απορία θα ξαναρωτήσω. Με LINQ έχω ασχοληθεί ελάχιστα (και τις περισσότερες φορές το χρησιμοποιούσα για να κάνω iterate σε containers AsList για να μπορώ να πειράζω τα πράγματα που είχαν μέσα), αλλά ό,τι μαθαίνει κανείς καλό είναι, και λέω να ξεκινήσω να μαθαίνω και C# λίγο καλύτερα.

 

Ευχαριστώ!

Δες yield return και ienumerable. 

[M2000]

Μούφα...πρόγραμμα.....και ο λόγος; Όταν έχεις βγάλει το πολλαπλάσια του 2, με πίνακα,  τότε δεν υπάρχουν ούτε του 4, ούτε του 8 κοκ...Οπότε ο σωστός αλγόριθμος ποτέ δεν θα πάει στο 4 για να βγάλει τα πολλαπλάσια!!!!!!
Defacer έλαβες Μαθηματικά...0

 

(την ρόμπα στην επιστρέφω...σιδερωμένη...)
 

Defacer
Εγώ θέλω να πάρω σαν αποτέλεσμα ένα enumerable που θα έχει μέσα όλα τα πολλαπλάσια του 2, και μετά όλα του 3, και μετά όλα του 4, κλπ μέχρι το sqrt(limit), πάντα για πολλαπλάσια <= limit. Αλλά για να το κάνω αυτό πρέπει να πολλαπλασιάσω. Τι πράγμα να πολλαπλασιάσω με τι, εφόσον μόνο για ένα νούμερο x έχουμε μιλήσει μέχρι τώρα;

[Επισκέπτης]

άσε τις ρομπες και τις εξυπνάδες και μάθε 2 πράγματα που θα έπρεπε να ξέρεις μετά από τόση ενασχόληση με τον προγραμματισμό:

 

ο Σωστός αλγόριθμος είναι αυτός που σε προγραμματιστικη υλοποίηση παράγει σωστό αποτέλεσμα και συνήθως δεν έχει κανένα/ελάχιστο περιορισμό.

 

Ο Βελτιστος αλγόριθμος εξαρτάται από τι θεωρείται βελτιστο κατά περίπτωση και συνήθως έχει περιορισμούς.

[M2000]

Έτσι σκέφτομαι και εγώ. Προφανώς χαριτολογώ και το ρόμπα το επέστρεψα. Αφού όμως λες για απλότητα, τότε η Basic του Amstrad αρκεί. Γιατί να το κουράσουμε με σπέσιαλ περίπτωση στη c#; Εκτός και αν ο σκοπός είναι κάτι περισσότερο από το να πάρουμε τους 100 πρώτους. Αν είναι τότε η προτροπή για βελτίωση...θα είναι επιθυμητή. Οκ υπάρχει και κάποιος που δεν θέλει..προκοπή. Θα ζήσουμε και με αυτό.

[AllCowsEatGrass]

Η υλοποίηση του def με την αλλαγή του TakeWhile που είπε, είναι λίγο πιο neat.

 

Note πως αντί για int.MaxValue έχω βάλει short.MaxValue σαν workaround, ο λόγος: 

public static IEnumerable<int> Range(
    int start,
    int count
)

ArgumentOutOfRangeException: start + count -1 is larger than MaxValue.

Ας το κάνει κάποιος και σε python με τον αντίστοιχο neat τρόπο να το δουμε!

[Επισκέπτης]

Δεν ανέφερα απλότητα. Πάντως στον

παραπάνω απλο κώδικα σε basic έχει bug από την 2η γραμμή. 32768