Primtal
Hej,
Säg att jag har en mäng som innehåller n-antal primtal. Till exempel:
Kan jag på något sätt se om inte innehåller ett primtal genom att enbart titta på hur övriga primtalen förhåller sig till varann, dvs. inte titta på om respektive element är delbara med sig själv och talet 1. Om så, kan ni vänligen förklara varför?
Allt gott,
/Hjortron
Alltså man kan ju bara generera en lista över alla primtal som finns upp till största talet i mängden och sedan jämföra primtalen som finns med talen i listan. Vad som är skillnaden mellan att jämföra tal i en lista med varandra och att jämföra med tal som ligger utanför listan är lite vagt.
Det är lite öppet vad du menar med 'förhåller sig till varandra', men det man kan göra är att kontrollera om talen är 'relativt prima'dvs om de saknas gemensamma delare större än 1.
Om man har en mängd av primtal så är de alltid relativt prima.
Ex: {2,5,7,19} är alla relativt prima
Om man har en mängd av tal som är relativt prima så behöver de dock inte alla vara primtal.
ex: {3,5, 14} är alla relativt prima men 14 är inte ett primtal.
Vad man kan göra med en lista är att snabbt utesluta talen som inte är relativt prima och därmed inte kan vara primtal. Om x och y är två tal sådana att x < y så kan man med euklides algoritm se vad deras gemensamma delare är och är delaren mindre än båda talen så är de inte primtal, och om delaren är det ena talet så kan man utesluta det större talet.
Exempelvis med listan
{3, 4, 8, 12, 25}
kan utesluta 8 och 12 som primtal då de är delbara med 4 och få ner listan till
{3,4,25}
men därefter är alla talen relativt prima och jämförelse dem emellan ger ingenting.
Jag skulle förvänta mig att problemet med att hitta största delmängden där talen är relativt prima har en snabbare algoritm är att hitta största delmängden där alla tal är primtal, men ska man hitta primtalen måste man i något steg börja involvera jämförelser som är lite svårare.
