Programma per trovare numeri primi
https://stackoverflow.com/questions/1510124
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Voglio trovare il numero primo compreso tra 0 e una lunga variabile, ma io non sono in grado di ottenere alcun output.
Il programma è
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication16
{
class Program
{
void prime_num(long num)
{
bool isPrime = true;
for (int i = 0; i <= num; i++)
{
for (int j = 2; j <= num; j++)
{
if (i != j && i % j == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
isPrime = true;
}
}
static void Main(string[] args)
{
Program p = new Program();
p.prime_num (999999999999999L);
Console.ReadLine();
}
}
}
Uno può darmi una mano e trovare ciò che è la possibile errore nel programma?
Soluzione
È possibile farlo più velocemente utilizzando un quasi ottimale divisione di prova setaccio in una linea (lunga) in questo modo:
Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
Enumerable.Range(2, num-1).ToList(),
(result, index) => {
var bp = result[index]; var sqr = bp * bp;
result.RemoveAll(i => i >= sqr && i % bp == 0);
return result;
}
);
La formula approssimazione per numero di primi utilizzata è π(x) < 1.26 x / ln(x) . Abbiamo solo bisogno di testare per primi non maggiore di x = sqrt(num) .
Si noti che il crivello di Eratostene ha molto meglio correre tempo la complessità di divisione di prova (dovrebbe funzionare molto più veloce per i più grandi num valori, se correttamente implementato).
Altri suggerimenti
Prova questo:
void prime_num(long num)
{
// bool isPrime = true;
for (long i = 0; i <= num; i++)
{
bool isPrime = true; // Move initialization to here
for (long j = 2; j < i; j++) // you actually only need to check up to sqrt(i)
{
if (i % j == 0) // you don't need the first condition
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
// isPrime = true;
}
}
Hai solo bisogno di controllare divisori dispari fino alla radice quadrata del numero. In altre parole, il vostro ciclo interno ha bisogno di iniziare:
for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }
È anche possibile uscire dalla funzione appena si trova il numero non è primo, non è necessario per verificare eventuali altri divisori (Vedo che stai già facendo!).
Questo funziona solo se num è più grande di due.
No Sqrt
È possibile evitare lo Sqrt del tutto mantenendo una somma parziale. Ad esempio:
int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}
Questo perché la somma dei numeri 1+ (3 + 5) + (7 + 9) vi darà una sequenza di quadrati dispari (1,9,25, ecc). E quindi j rappresenta la radice quadrata di square_sum. Finché square_sum è inferiore i allora j è inferiore alla radice quadrata.
La gente ha menzionato un paio di elementi costitutivi verso fare questo in modo efficace, ma nessuno è davvero mettere insieme i pezzi. I href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" di Eratostene è un buon inizio, ma con esso vi corto di memoria < em> lunga prima di raggiungere il limite che hai impostato. Questo non significa che è inutile anche se - quando stai facendo il tuo ciclo, quello che si ha realmente a cuore sono divisori primi. Come tale, è possibile avviare utilizzando il setaccio per creare una base di divisori primi, quindi utilizzare quelli del ciclo per testare i numeri per il primato.
Quando si scrive il ciclo, però, davvero non si vuole noi sqrt (i) nella condizione del ciclo come un paio di risposte hanno suggerito. Tu ed io sappiamo che lo sqrt è una funzione "pura" che dà sempre la stessa risposta se dato lo stesso parametro di ingresso. Purtroppo, il compilatore non sa che, quindi, se si usa qualcosa come '<= Math.sqrt (x)' nella condizione del ciclo, sarà ri-calcolare la radice quadrata del numero ogni iterazione del ciclo.
È possibile evitare che un paio di modi diversi. È possibile pre-calcolare la radice quadrata prima del ciclo, e utilizzare il valore pre-calcolate nella condizione del ciclo, oppure si può lavorare nella direzione opposta, e cambiare i<Math.sqrt(x) a i*i<x. Personalmente, mi piacerebbe pre-Calcola la radice quadrata anche se - penso che sia più chiaro e probabilmente un po 'più veloce - ma che dipende dal numero di iterazioni del ciclo (il i*i significa che è ancora facendo una moltiplicazione nel loop). Con solo pochi iterazioni, i*i sarà tipicamente più veloce. Con abbastanza iterazioni, la perdita da i*i ad ogni iterazione supera il tempo per l'esecuzione di sqrt una volta fuori dal giro.
Questa è probabilmente adeguata per le dimensioni dei numeri hai a che fare con - un limite di 15 cifre intende la radice quadrata è di 7 o 8 cifre, che si inserisce in un abbastanza ragionevole quantità di memoria. D'altra parte, se si vuole fare con i numeri in questa fascia di molto, si potrebbe desiderare di guardare ad alcuni dei più sofisticati algoritmi di prima serata di controllo, come ad esempio algoritmi di Pollard o Brent di . Questi sono più complessi (per usare un eufemismo), ma un molto più veloce per i grandi numeri.
Ci sono altri algoritmi per i numeri ancora più grandi ( quadratica setaccio , numero generale campo setaccio ) ma noi non entreremo in loro per il momento - sono molto più complesso , e davvero utile solo per affrontare davvero grandi numeri (il GNFS comincia ad essere utile nel range 100 + cifre).
Primo passo: scrivere un metodo di estensione per scoprire se un ingresso è primo
public static bool isPrime(this int number ) {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
2 step: scrivere il metodo che stamperà tutti i numeri primi che sono tra 0 e l'ingresso numero di
public static void getAllPrimes(int number)
{
for (int i = 0; i < number; i++)
{
if (i.isPrime()) Console.WriteLine(i);
}
}
Potrebbe essere solo la mia opinione, ma c'è un altro grave errore nel programma (mettendo da parte il dato 'numero primo' domanda, che è stato accuratamente risposto).
Come il resto dei soccorritori, sto assumendo questo è compiti a casa, che indica vuoi diventare uno sviluppatore (presumibilmente).
È necessario imparare a compartimenti stagni codice. Non è qualcosa che avrete sempre bisogno di fare in un progetto, ma è bene sapere come farlo.
Il tuo metodo prime_num (lungo num) poteva sopportare una migliore, nome più descrittivo. E se si suppone di trovare tutti i numeri primi meno di un dato numero, dovrebbe restituirli sotto forma di elenco. Questo rende più facile per separare il display e la funzionalità.
Se semplicemente restituito un IList contenente i numeri primi si potrebbe poi visualizzare nella vostra funzione principale (forse chiamare un'altra funzione al di fuori di stamparli abbastanza) o utilizzarli in ulteriori calcoli su tutta la linea.
Quindi la mia raccomandazione migliore per voi è quello di fare qualcosa di simile:
public void main(string args[])
{
//Get the number you want to use as input
long x = number;//'number' can be hard coded or retrieved from ReadLine() or from the given arguments
IList<long> primes = FindSmallerPrimes(number);
DisplayPrimes(primes);
}
public IList<long> FindSmallerPrimes(long largestNumber)
{
List<long> returnList = new List<long>();
//Find the primes, using a method as described by another answer, add them to returnList
return returnList;
}
public void DisplayPrimes(IList<long> primes)
{
foreach(long l in primes)
{
Console.WriteLine ( "Prime:" + l.ToString() );
}
}
Anche se si finisce per lavorare in un posto dove speration come questo non è necessario, è bene sapere come farlo.
EDIT_ADD: Se Will Ness è corretto che lo scopo della domanda è solo quello di produrre un flusso continuo di numeri primi fino a quando il programma viene eseguito (premendo Pausa / Pausa per mettere in pausa e un tasto per avviare ancora una volta) senza gravi speranza di ogni arrivare a quel limite superiore, allora il codice dovrebbe essere scritto senza argomenti limite superiore e un test di ricezione di "vero" per la prima 'i' per il ciclo. D'altra parte, se la domanda ha voluto stampare in realtà i numeri primi fino a un limite, quindi il seguente codice farà il lavoro molto più efficiente utilizzando Divisione di prova solo per i numeri dispari, con il vantaggio che non fa uso di memoria a tutti (potrebbe anche essere convertita in un ciclo continuo come da sopra):
static void primesttt(ulong top_number) {
Console.WriteLine("Prime: 2");
for (var i = 3UL; i <= top_number; i += 2) {
var isPrime = true;
for (uint j = 3u, lim = (uint)Math.Sqrt((double)i); j <= lim; j += 2) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) Console.WriteLine("Prime: {0} ", i);
}
}
Innanzitutto, il codice questione produce alcuna uscita a causa di che le sue variabili di loop sono interi e il limite testato è un intero lungo enorme, che significa che è impossibile per il ciclo di raggiungere il limite di produzione di un ciclo interno CURA: per cui la 'j' variabile loop indietro intorno ai numeri negativi; quando la variabile 'j' ritorna intorno a -1, il numero di testate non supera il test privilegiata, perché tutti i numeri sono divisibile per -1 END_EDIT . Anche se ciò fosse corretto, il codice domanda produce un output molto lento perché viene legato per fare le divisioni a 64 bit di grandi quantità di numeri composti (tutti i numeri pari più i compositi dispari) per tutta la gamma dei numeri fino a quel top numero di dieci elevato alla potenza XVI per ogni serata che si può eventualmente produrre. Il codice precedente funziona perché limita il calcolo ai soli numeri dispari e fa solo divisioni di rollover fino alla radice quadrata del numero corrente in prova .
Questa operazione richiede un'ora o giù di lì per visualizzare i numeri primi fino a un miliardo, così si può immaginare la quantità di tempo necessario per mostrare tutti i numeri primi a diecimila trilioni di (10 elevato alla potenza sedicesimo), tanto più che la il calcolo diventa più lento con l'aumentare gamma. END_EDIT_ADD
Anche se l'uno di linea (tipo di) risposta da @SLaks utilizzando LINQ funziona, in realtà non è il crivello di Eratostene in quanto è solo una versione unoptimised di Sezione di primo grado , unoptimised in quanto non elimina primi dispari, non inizia presso la piazza del primo di base trovata, e non si ferma posteriore per Base innesca maggiore della radice quadrata del numero superiore a setaccio. E 'anche abbastanza lento a causa delle molteplici operazioni nidificato enumerazione.
Si tratta infatti di un abuso del metodo Linq aggregata e non usa effettivamente il primo dei due Linq Range generato. Può diventare una Divisione di prova ottimizzata con meno overhead enumerazione come segue:
static IEnumerable<int> primes(uint top_number) {
var cullbf = Enumerable.Range(2, (int)top_number).ToList();
for (int i = 0; i < cullbf.Count; i++) {
var bp = cullbf[i]; var sqr = bp * bp; if (sqr > top_number) break;
cullbf.RemoveAll(c => c >= sqr && c % bp == 0);
} return cullbf; }
che va molte volte più veloce rispetto alle SLaks risposta. Tuttavia, è ancora lento e intensivo di memoria dovuta alla generazione List e le enumerazioni multiple nonché il divario multiplo (implicita nel modulo) operazioni.
Il seguente vera crivello di attuazione Eratostene gestisce circa 30 volte più veloce e richiede molto meno memoria in quanto utilizza dall'originale un bit per numero setacciata e limita la sua censimento al risultato finale sequenza iteratore, nonché avente le ottimizzazioni di solo trattamento compositi dispari, e solo abbattimento dei quadrati dei numeri primi di base per la base di numeri primi fino alla radice quadrata del numero massimo, come segue:
static IEnumerable<uint> primes(uint top_number) {
if (top_number < 2u) yield break;
yield return 2u; if (top_number < 3u) yield break;
var BFLMT = (top_number - 3u) / 2u;
var SQRTLMT = ((uint)(Math.Sqrt((double)top_number)) - 3u) / 2u;
var buf = new BitArray((int)BFLMT + 1,true);
for (var i = 0u; i <= BFLMT; ++i) if (buf[(int)i]) {
var p = 3u + i + i; if (i <= SQRTLMT) {
for (var j = (p * p - 3u) / 2u; j <= BFLMT; j += p)
buf[(int)j] = false; } yield return p; } }
Il codice sopra calcola tutti i numeri primi per dieci milioni di gamma in circa 77 millisecondi su un processore Intel i7-2700K (3.5 GHz).
Uno dei due metodi statici possono essere chiamati e testato con le istruzioni using e con il metodo statico main come segue:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
static void Main(string[] args) {
Console.WriteLine("This program generates prime sequences.\r\n");
var n = 10000000u;
var elpsd = -DateTime.Now.Ticks;
var count = 0; var lastp = 0u;
foreach (var p in primes(n)) { if (p > n) break; ++count; lastp = (uint)p; }
elpsd += DateTime.Now.Ticks;
Console.WriteLine(
"{0} primes found <= {1}; the last one is {2} in {3} milliseconds.",
count, n, lastp,elpsd / 10000);
Console.Write("\r\nPress any key to exit:");
Console.ReadKey(true);
Console.WriteLine();
}
che mostrerà il numero di primi nella sequenza fino al limite, il last Prime trovato, e il tempo speso nella enumerazione che lontano.
EDIT_ADD: Tuttavia, al fine di produrre un censimento del numero di primi minori di diecimila trilioni (dieci alla potenza XVI) come questione si chiede, un approccio paging segmentato utilizzando multi-core trasformazione è necessaria ma anche con C ++ e molto altamente ottimizzato PrimeSieve , ciò richiederebbe qualcosa oltre 400 ore per produrre solo il numero di numeri primi trovati, e decine di volte che lungo enumerare tutti loro in modo più di un anno di fare ciò che la domanda chiede. Per farlo utilizzando la Sezione di primo grado algoritmo di non-ottimizzate tentato, ci vorrà eoni eccellenti e un tempo molto molto lungo, anche utilizzando un algoritmo Sezione di primo grado ottimizzato come in qualcosa come dieci a due anni di potere milionesimo (che è di due milioni di zeri anni !! !).
Non è molto da stupirsi che la sua macchina desktop appena seduto e in fase di stallo, quando ha provato !!!! Se avesse tentato una gamma più ridotta, come un milione, ha ancora avrebbe trovato che ci vuole nella gamma di secondi come attuato.
Le soluzioni che inserisco qui non è tagliato o come anche l'ultimo Crivello di Eratostene uno richiederà circa 640 terabyte di memoria per tale intervallo.
Ecco perché solo una pagina di approccio segmentato come quello di PrimeSieve in grado di gestire questo tipo di problema per la gamma, come specificato a tutti, e anche questo richiede un tempo molto lungo, come in settimane o anni se non si ha accesso a un super-computer con centinaia di migliaia di core. END_EDIT_ADD
Puzza di più compiti a casa. Il mio molto molto vecchio calcolatrice grafica ha avuto un programma è il primo del genere. Technnically il ciclo interno devision controllo deve solo correre i ^ (1/2). Avete bisogno di trovare "tutti" i numeri primi compresi tra 0 e L? L'altro problema principale è che le variabili di loop sono "int", mentre i dati di input è "lungo", questo sarà causando un overflow fare i loop non riescono ad eseguire anche una sola volta. Fissare le variabili del loop.
Un codice di linea in C #: -
Console.WriteLine(String.Join(Environment.NewLine,
Enumerable.Range(2, 300)
.Where(n => Enumerable.Range(2, (int)Math.Sqrt(n) - 1)
.All(nn => n % nn != 0)).ToArray()));
Il Crivello di Eratostene rispondere di cui sopra non è del tutto corretto. Come scritto troverà tutti i numeri primi tra 1 e 1000000. Per trovare tutti i numeri primi tra 1 e uso num:
private static IEnumerable Primes01(int num)
{
return Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num))))
.Aggregate(Enumerable.Range(1, num).ToList(),
(result, index) =>
{
result.RemoveAll(i => i > result[index] && i%result[index] == 0);
return result;
}
);
}
Il seme della aggregata dovrebbe essere compreso tra 1 e num dal momento che questo elenco conterrà l'elenco definitivo dei numeri primi. Il Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) è il numero di volte che il seme viene spurgato.
ExchangeCore Forum hanno una buona applicazione console elencato che sembra di scrivere numeri primi trovati in un file, sembra che si può anche utilizzare lo stesso file come punto di partenza in modo che non è necessario riavviare trovare numeri primi da 2 e forniscono un download del file con tutti trovati i numeri primi fino a 100 milioni, quindi sarebbe un buon inizio.
L'algoritmo sulla pagina prende anche un paio di scorciatoie (numeri dispari e solo controlla fino alla radice quadrata) che lo rende estremamente efficiente e vi permetterà di calcolare numeri lunghi.
quindi questo è fondamentalmente solo due errori di battitura , uno, il più sfortunato, for (int j = 2; j <= num; j++) che è la ragione per la sperimentazione improduttivo di 1%2,1%3 ... 1%(10^15-1), che va avanti per molto tempo in modo che il PO non ha ottenuto < em> "qualsiasi uscita" . dovrebbe essere rimasto j < i; invece L'altro, un minore in confronto, è che i dovrebbe iniziare da 2, non da 0:.
for( i=2; i <= num; i++ )
{
for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough
....
Di certo non si può ragionevolmente aspettare da un console di stampa-out di 28 trilioni di numeri primi o giù di lì per essere completato in qualsiasi lasso di tempo ragionevole. Così, l'intento originale del problema era ovviamente per stampare un flusso costante di numeri primi, a tempo indeterminato . Quindi tutte le soluzioni che propongono la semplicità d'uso crivello di Eratostene sono totalmente senza merito qui, perché semplice crivello di Eratostene è delimitato - un limite deve essere impostato in anticipo.
Che cosa potrebbe lavorare qui è la divisione ottimizzato processo che avrebbe salvato i numeri primi in quanto li trova, e la prova contro i primi, non solo tutti i numeri al di sotto del candidato.
In secondo luogo alternativo, con molto meglio la complessità (cioè molto più veloce) è quello di utilizzare un setaccio segmentato di Eratostene . Che è incrementale e senza limiti.
Entrambi questi sistemi userebbero produzione doppio scena di primi : si potrebbe produrre e salvare i primi, per essere utilizzati da altra fase di test (o setacciatura), molto al di sopra del limite del prima fase (sotto il suo quadrato ovviamente - estendere automaticamente la prima fase, come la seconda fase sarebbe sempre più in alto).
Per essere sinceri, alcune delle soluzioni proposte sono molto lento, e quindi sono cattivi suggerimenti. Per testare un singolo numero per essere primo avete bisogno di qualche operatore di divisione / modulo, ma per il calcolo di una serie che non è necessario.
In pratica è sufficiente escludere i numeri che sono multipli di numeri primi in precedenza trovato, come sono (per definizione) non innesca se stessi.
Non darò la piena attuazione, come sarebbe a facile, questo è l'approccio in pseudo codice. (Nella mia macchina, l'effettiva attuazione calcola tutti i primi in Sytem.Int32 (2 bilion) entro 8 secondi.
public IEnumerable<long> GetPrimes(long max)
{
// we safe the result set in an array of bytes.
var buffer = new byte[long >> 4];
// 1 is not a prime.
buffer[0] = 1;
var iMax = (long)Math.Sqrt(max);
for(long i = 3; i <= iMax; i +=2 )
{
// find the index in the buffer
var index = i >> 4;
// find the bit of the buffer.
var bit = (i >> 1) & 7;
// A not set bit means: prime
if((buffer[index] & (1 << bit)) == 0)
{
var step = i << 2;
while(step < max)
{
// find position in the buffer to write bits that represent number that are not prime.
}
}
// 2 is not in the buffer.
yield return 2;
// loop through buffer and yield return odd primes too.
}
}
La soluzione richiede una buona comprensione delle operazioni bit per bit. Ma vie, ei metodi più veloci. È inoltre possibile al sicuro il risultato del risultato su disco, se ne avete bisogno per un uso successivo. Il risultato di 17 * 10 ^ 9 numeri può essere SAFED con 1 GB, e il calcolo di detto insieme di risultati richiede circa 2 minuti max.
So che questo è tranquilla vecchia questione, ma dopo aver letto qui: Crivello di Eratostene Wiki
Questo è il modo in cui ho scritto di comprendere l'algoritmo:
void SieveOfEratosthenes(int n)
{
bool[] primes = new bool[n + 1];
for (int i = 0; i < n; i++)
primes[i] = true;
for (int i = 2; i * i <= n; i++)
if (primes[i])
for (int j = i * 2; j <= n; j += i)
primes[j] = false;
for (int i = 2; i <= n; i++)
if (primes[i]) Console.Write(i + " ");
}
Nel primo ciclo riempiamo l'array di booleani con vera.
secondo ciclo inizia dal 2 dal 1 non è un numero primo e verificherà se numero primo non è ancora cambiata e quindi assegnare falsa all'indice di j.
ultimo ciclo che abbiamo appena a stampare quando è primo.
Molto simile - da un esercizio di implementare Crivello di Eratostene in C #:
public class PrimeFinder
{
readonly List<long> _primes = new List<long>();
public PrimeFinder(long seed)
{
CalcPrimes(seed);
}
public List<long> Primes { get { return _primes; } }
private void CalcPrimes(long maxValue)
{
for (int checkValue = 3; checkValue <= maxValue; checkValue += 2)
{
if (IsPrime(checkValue))
{
_primes.Add(checkValue);
}
}
}
private bool IsPrime(long checkValue)
{
bool isPrime = true;
foreach (long prime in _primes)
{
if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
{
isPrime = false;
break;
}
}
return isPrime;
}
}
Primo Helper calcolo molto veloce
public static class PrimeHelper
{
public static IEnumerable<Int32> FindPrimes(Int32 maxNumber)
{
return (new PrimesInt32(maxNumber));
}
public static IEnumerable<Int32> FindPrimes(Int32 minNumber, Int32 maxNumber)
{
return FindPrimes(maxNumber).Where(pn => pn >= minNumber);
}
public static bool IsPrime(this Int64 number)
{
if (number < 2)
return false;
else if (number < 4 )
return true;
var limit = (Int32)System.Math.Sqrt(number) + 1;
var foundPrimes = new PrimesInt32(limit);
return !foundPrimes.IsDivisible(number);
}
public static bool IsPrime(this Int32 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this Int16 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this byte number)
{
return IsPrime(Convert.ToInt64(number));
}
}
public class PrimesInt32 : IEnumerable<Int32>
{
private Int32 limit;
private BitArray numbers;
public PrimesInt32(Int32 limit)
{
if (limit < 2)
throw new Exception("Prime numbers not found.");
startTime = DateTime.Now;
calculateTime = startTime - startTime;
this.limit = limit;
try { findPrimes(); } catch{/*Overflows or Out of Memory*/}
calculateTime = DateTime.Now - startTime;
}
private void findPrimes()
{
/*
The Sieve Algorithm
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
numbers = new BitArray(limit, true);
for (Int32 i = 2; i < limit; i++)
if (numbers[i])
for (Int32 j = i * 2; j < limit; j += i)
numbers[j] = false;
}
public IEnumerator<Int32> GetEnumerator()
{
for (Int32 i = 2; i < 3; i++)
if (numbers[i])
yield return i;
if (limit > 2)
for (Int32 i = 3; i < limit; i += 2)
if (numbers[i])
yield return i;
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
// Extended for Int64
public bool IsDivisible(Int64 number)
{
var sqrt = System.Math.Sqrt(number);
foreach (var prime in this)
{
if (prime > sqrt)
break;
if (number % prime == 0)
{
DivisibleBy = prime;
return true;
}
}
return false;
}
private static DateTime startTime;
private static TimeSpan calculateTime;
public static TimeSpan CalculateTime { get { return calculateTime; } }
public Int32 DivisibleBy { get; set; }
}
public static void Main()
{
Console.WriteLine("enter the number");
int i = int.Parse(Console.ReadLine());
for (int j = 2; j <= i; j++)
{
for (int k = 2; k <= i; k++)
{
if (j == k)
{
Console.WriteLine("{0}is prime", j);
break;
}
else if (j % k == 0)
{
break;
}
}
}
Console.ReadLine();
}
static void Main(string[] args)
{ int i,j;
Console.WriteLine("prime no between 1 to 100");
for (i = 2; i <= 100; i++)
{
int count = 0;
for (j = 1; j <= i; j++)
{
if (i % j == 0)
{ count=count+1; }
}
if ( count <= 2)
{ Console.WriteLine(i); }
}
Console.ReadKey();
}
U può usare il normale numero primo concetto deve solo due fattori (uno e se stesso). Quindi fare come questo, modo semplice
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PrimeNUmber
{
class Program
{
static void FindPrimeNumber(long num)
{
for (long i = 1; i <= num; i++)
{
int totalFactors = 0;
for (int j = 1; j <= i; j++)
{
if (i % j == 0)
{
totalFactors = totalFactors + 1;
}
}
if (totalFactors == 2)
{
Console.WriteLine(i);
}
}
}
static void Main(string[] args)
{
long num;
Console.WriteLine("Enter any value");
num = Convert.ToInt64(Console.ReadLine());
FindPrimeNumber(num);
Console.ReadLine();
}
}
}
Questa soluzione visualizza tutti i numeri primi tra 0 e 100.
int counter = 0;
for (int c = 0; c <= 100; c++)
{
counter = 0;
for (int i = 1; i <= c; i++)
{
if (c % i == 0)
{ counter++; }
}
if (counter == 2)
{ Console.Write(c + " "); }
}
Questo è il modo più veloce per calcolare i numeri primi in C #.
void PrimeNumber(long number)
{
bool IsprimeNumber = true;
long value = Convert.ToInt32(Math.Sqrt(number));
if (number % 2 == 0)
{
IsprimeNumber = false;
}
for (long i = 3; i <= value; i=i+2)
{
if (number % i == 0)
{
// MessageBox.Show("It is divisible by" + i);
IsprimeNumber = false;
break;
}
}
if (IsprimeNumber)
{
MessageBox.Show("Yes Prime Number");
}
else
{
MessageBox.Show("No It is not a Prime NUmber");
}
}
class CheckIfPrime
{
static void Main()
{
while (true)
{
Console.Write("Enter a number: ");
decimal a = decimal.Parse(Console.ReadLine());
decimal[] k = new decimal[int.Parse(a.ToString())];
decimal p = 0;
for (int i = 2; i < a; i++)
{
if (a % i != 0)
{
p += i;
k[i] = i;
}
else
p += i;
}
if (p == k.Sum())
{ Console.WriteLine ("{0} is prime!", a);}
else
{Console.WriteLine("{0} is NOT prime", a);}
}
}
}
Ci sono alcuni modi molto ottimali per implementare l'algoritmo. Ma se non si sa molto su calcoli e sufficiente seguire la definizione di primaria come il requisito: un numero che è divisibile solo per 1 e per se stessa (e nient'altro), ecco una semplice da capire il codice per i numeri positivi.
public bool IsPrime(int candidateNumber)
{
int fromNumber = 2;
int toNumber = candidateNumber - 1;
while(fromNumber <= toNumber)
{
bool isDivisible = candidateNumber % fromNumber == 0;
if (isDivisible)
{
return false;
}
fromNumber++;
}
return true;
}
Poiché ogni numero è divisibile per 1 e per sé, si parte da controllare 2 in avanti fino a che il numero immediatamente prima di se stesso. Questo è il ragionamento di base.
Si può fare anche questo:
class Program
{
static void Main(string[] args)
{
long numberToTest = 350124;
bool isPrime = NumberIsPrime(numberToTest);
Console.WriteLine(string.Format("Number {0} is prime? {1}", numberToTest, isPrime));
Console.ReadLine();
}
private static bool NumberIsPrime(long n)
{
bool retVal = true;
if (n <= 3)
{
retVal = n > 1;
} else if (n % 2 == 0 || n % 3 == 0)
{
retVal = false;
}
int i = 5;
while (i * i <= n)
{
if (n % i == 0 || n % (i + 2) == 0)
{
retVal = false;
}
i += 6;
}
return retVal;
}
}
