Almeno 4 primi

Un bel problemino, trovato nel sito Euler, già citato in questo blog qualche tempo fa, parla di divisibilità e di numeri primi: argomenti alquanto interessanti, specialmente per i ragazzi di 3A che si dilettano di programmazione in Python.

Ecco quindi il problema (semplificato per questioni didattiche):

Verificare (e trovare) che ci sono 23 numeri positivi minori di 1000 che sono divisibili per almeno 4 primi distinti minori di 100.

Esempio: 210 = 2*3*5*7 ma anche 420= 2*2*3*5*7 ecc.

Ricchi premi agli studenti che mi inviano un bel programma che risolve il problema.

P.S.

Per chi si sente forte, il problema può essere esteso sostituendo 1000 con 10000 o 100000 ecc fino a 10^{16}.

Advertisements
Questa voce è stata pubblicata in Algoritmi, Aritmetica, Informatica, M3, M3.0910, Matematica, Matematica.curiosa, Teoria dei numeri e contrassegnata con , . Contrassegna il permalink.

5 risposte a Almeno 4 primi

  1. edoardobastianetto ha detto:

    Con questo invece si può scegliere fino a che numero cercare e il numero minimo di divisori primi che deve avere il numero.
    Codice in VB.NET
    —————————————
    Text1 contiene “Fino a che numero cercare”
    NDivisori (textbox) contiene il numero minimo di divisori
    Command3 è il bottone per eseguire
    text2 è la lista dei numeri trovati
    NRisultati(textbox) è la quantità dei numeri trovati
    —————————————
    —————————————
    Public Class Form1

    Dim NumeroMax As Long
    Dim NumeroDivisori As Long

    Private Sub TrovaNumeriValidi()

    Text2.Text = “”
    Dim Ndivisori As Long
    Dim numero As Long
    Dim NNumeriValidi As Long

    NNumeriValidi = 0

    Dim Primi() As Long ‘ Numeri Primi da 2 al numero dato
    Dim PrimiMax As Long ‘ Quanti numeri primi ho trovato

    Dim i As Long
    ‘ Cerco i numeri primi fino al numero dato e li salvo su “Primi”
    For i = 2 To NumeroMax
    If Isprimo(i) = True Then
    PrimiMax += 1
    ReDim Preserve Primi(0 To PrimiMax)
    Primi(PrimiMax) = i
    End If
    Next i

    For numero = 1 To NumeroMax
    Ndivisori = 0

    Dim j As Integer
    For j = 1 To PrimiMax
    i = Primi(j)
    If numero / i = numero \ i Then Ndivisori = Ndivisori + 1
    Next j

    If Ndivisori >= NumeroDivisori Then
    Text2.Text = Text2.Text & vbCrLf & numero
    NNumeriValidi = NNumeriValidi + 1
    End If

    Next numero

    Nrisultati.Text = NNumeriValidi

    End Sub

    Private Function Isprimo(ByVal numero As Long) As Boolean

    Dim i As Long

    For i = 2 To numero – 1
    If numero / i = numero \ i Then
    Isprimo = False
    Exit Function
    End If
    Next i

    Isprimo = True

    End Function

    Private Sub Command3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Command3.Click
    Call TrovaNumeriValidi()
    MsgBox(“fine”)

    End Sub

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
    NumeroDivisori = Ndivisori.Text
    NumeroMax = Text1.Text
    End Sub

    Private Sub Ndivisori_TextChanged(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Ndivisori.TextChanged
    NumeroDivisori = Ndivisori.Text
    End Sub

    Private Sub Text1_TextChanged(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Text1.TextChanged
    NumeroMax = Text1.Text
    End Sub
    End Class

  2. Edoardo Bastianetto ha detto:

    ‘all’inizio bisogna creare sul form un textbox che in questo caso è chiamato Numeri, serve per verificare che in tutto ci siano 23 numeri che rispondono a queste richieste

    ———————————————————————————
    Option Explicit

    Private Sub Form_Load()
    TrovaNumeriValidi
    End Sub

    Private Sub TrovaNumeriValidi()
    Dim NDivisori As Integer
    Dim Numero As Integer
    Dim NNumeriValidi As Integer

    NNumeriValidi = 0
    For Numero = 1 To 1000
    NDivisori = 0

    If Numero / 2 = Numero \ 2 Then NDivisori = NDivisori + 1
    If Numero / 3 = Numero \ 3 Then NDivisori = NDivisori + 1
    If Numero / 5 = Numero \ 5 Then NDivisori = NDivisori + 1
    If Numero / 7 = Numero \ 7 Then NDivisori = NDivisori + 1
    If Numero / 11 = Numero \ 11 Then NDivisori = NDivisori + 1
    If Numero / 13 = Numero \ 13 Then NDivisori = NDivisori + 1
    If Numero / 17 = Numero \ 17 Then NDivisori = NDivisori + 1
    If Numero / 19 = Numero \ 19 Then NDivisori = NDivisori + 1
    If Numero / 23 = Numero \ 23 Then NDivisori = NDivisori + 1
    If Numero / 29 = Numero \ 29 Then NDivisori = NDivisori + 1
    If Numero / 31 = Numero \ 31 Then NDivisori = NDivisori + 1

    ( 1000 / ( 2*3*5) = 1000 / 30 = 33,33periodico quindi basta usare i numeri primi sotto il numero 33 altrimenti il numero sarebbe maggiore a 1000..)

    If NDivisori > 3 Then
    Debug.Print Numero (‘così si può vedere quali sono)
    NNumeriValidi = NNumeriValidi + 1
    End If

    Next Numero

    Numeri.Text = NNumeriValidi

    End Sub
    ————————————————————————–

    Proffessore se vuole per esercizio potrei provare a farlo più generico

  3. Edoardo Bastianetto ha detto:

    Io ho provato a farlo in vb 6 perchè Python non lo so usare , è venuto molto lungo, lo posso pubblicare lo stesso ?

  4. Dennis Rodman ha detto:

    Qui nessuno risponde.. Vorrei dare un po’ di suggerimenti. Per come l’ho pensata io il problema si potrebbe risolvere sfruttando 2 elementi:

    1) Una funzione booleana, che, preso in input un valore numerico intero > 1 mi restituisca TRUE se è primo o FALSE se è falso. Questa ipotetica funzione la chiamerei isPrimo(n).

    2)Una funzione che prenda come parametro di ingresso il valore di partenza per la ricerca (1000 per cominciare, poi 10000, poi 100000.. Finchè la RAM del pc non ci supplicherà pietà insomma) e che restituisca una LISTA contenente i famosi numeri aventi almeno 4 primi distinti come divisori. Una volta ottenuta la lista, basterà visualizzarla per conoscere i numeri trovati. Per conoscere quanti sono si potrebbe usare una funzione del tipo lenght(lista) che sicuramente il Python mette a disposizione.

    Provo a proporre una bozza della prima funzione (la isPrimo(n)) in pseudocodifica.

    funzione isPrimo(n):boolean
    inizio
    i=2;
    trovatoDiv=false;
    se n==2 allora restituisci TRUE
    altrimenti finchè (i<n) e NON(trovatoDiv) do
    se n MOD i =0 allora {
    trovatoDiv=true
    restituisci FALSE
    }
    altrimenti i++
    restituisci TRUE
    fine

    Questa funzioncina l'ho scritta al volo. C'è un sistema per ottimizzarla, ma non voglio togliervi il gusto. Buon divertimento ragazzi! Buonanotte..

  5. Dennis Rodman ha detto:

    Easy

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...