Mees doeltreffende kode vir die eerste 10000 eerste getalle?
https://stackoverflow.com/questions/622
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianVra
Ek wil om te druk die eerste 10000 eerste getalle.Kan iemand gee my die mees doeltreffende kode vir hierdie?Verduideliking:
- Dit maak nie saak as jou kode is ondoeltreffend vir n >10000.
- Die grootte van die kode nie saak nie.
- Jy kan nie net hard-kode van die waardes in enige manier.
Oplossing
Die Sif van Atkin is waarskynlik wat jy soek vir, sy bogrens loop van die tyd is O(N/log log N).
As jy net hardloop die getalle 1 meer en 1 minder as die veelvoude van 6, dit kan selfs vinniger, as al die eerste getalle bo 3 1 weg van sommige verskeie van ses.Hulpbron vir my verklaring
Ander wenke
Ek beveel'n sif, óf die Sif van Eratosthenes of die Sif van Atkin.
Die sif of Eratosthenes is waarskynlik die mees intuïtief metode van die vind van'n lys van die primes.Basies jy:
- Skryf'n lys van die nommers van 2 tot wat ook al beperking wat jy wil, laat ons sê 1000.
- Neem die eerste getal wat nie oorgesteek af (vir die eerste iterasie dit is 2) en kruis al die veelvoude van die getal van die lys.
- Herhaal stap 2 totdat jy bereik die einde van die lys.Al die getalle wat nie oorgesteek af is eerste.
Dit is duidelik dat daar is'n hele paar optimalisaties wat gedoen kan word om hierdie algoritme werk vinniger, maar dit is die basiese idee.
Die sif van Atkin gebruik van'n soortgelyke benadering, maar ongelukkig het ek weet nie genoeg oor dit om te verduidelik dit aan jou.Maar ek weet dat die algoritme wat ek gekoppel neem 8 sekondes om uit te vind al die primes tot 1000000000 op'n antieke Pentium II-350
Sif van Eratosthenes Bron-Kode: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Sif van Atkin Bron-Kode: http://cr.yp.to/primegen.html
Dit is nie streng teen die hardcoding beperking, maar kom verskriklik naby.Hoekom nie programatically aflaai van hierdie lys en druk dit uit, in plaas?
GateKiller, hoe oor die byvoeging van'n break om te dat if in die foreach lus?Wat sou bespoedig dinge 'n baie want as soos 6 is deelbaar deur 2 jy hoef nie te gaan met 3 en 5.(Ek wil stem jou oplossing in elk geval, as ek genoeg gehad reputasie :-) ...)
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
break;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
In die maatskappy haskell, kan ons skryf amper woord vir woord die wiskundige definisie van die sif van Eratosthenes, "primes is natuurlike getalle bo 1 sonder enige saamgestelde getalle, waar samestellings is gevind deur opsomming van elke eerste is veelvoude":
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000 is naby-oombliklike.
Verwysings:
Die bogenoemde kode is maklik tweaked in die werk op net kans, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)).Tyd kompleksiteit is baie verbeter (om net oor'n teken faktor bo optimale) deur die vou in'n boom-agtige struktuur, en ruimte kompleksiteit is drasties verbeter deur trap primes produksie, in
primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
where
_Y g = g (_Y g) -- non-sharing fixpoint combinator
_U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat
pairs (xs:ys:t) = union xs ys : pairs t
sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s,
| otherwise = sieve (k+2) xs -- when s⊂[k,k+2..]
(In maatskappy haskell die hakies word gebruik vir die groepering, 'n funksie oproep is te kenne gegee net deur die jukstaposisie, (:) is'n nadele operateur vir lyste, en (.) is'n funksionele samestelling operateur: (f . g) x = (\y -> f (g y)) x = f (g x)).
@Matt:aanteken(log(10000)) is ~2
Vanaf die wikipedia artikel (wat jy aangehaal) Sif van Atkin:
Hierdie sif bere primes tot N met behulp van
O(N/log log N)bedrywighede met net N1/2+o(1) stukkies van die geheue.Dit is 'n bietjie beter as die sif van Eratosthenes wat gebruik maak vanO(N)bedrywighede en O(N1/2(log log N)/teken N) stukkies van die geheue (A. O. L.Atkin, D. J.Bernstein, 2004).Hierdie asimptotiese computational kompleksiteit sluit eenvoudige optimalisaties, soos die wiel factorization, en die splitsing van die berekening te kleiner blokke.
Gegewe asimptotiese computational kompleksiteit saam O(N) (vir Eratosthenes) en O(N/log(log(N))) (vir Atkin) ons kan nie sê (vir klein N=10_000 watter algoritme indien geïmplementeer sal vinniger wees.
Achim Flammenkamp geskryf in Die Sif van Eratosthenes:
aangehaal deur:
@num1
Vir groter intervalle oor 10^9, sekerlik vir diegene > 10^10, die Sif van Eratosthenes is geklop deur die Sif van Atkins en Bernstein wat gebruik onverminderbare binêre kwadratiese vorms.Sien hul papier vir die agtergrond inligting sowel as paragraaf 5 van W.Galway se Ph. D.proefskrif.
Daarom vir 10_000 Sif van Eratosthenes kan vinniger wees dan Sif van Atkin.
Om te antwoord OP die kode is prime_sieve.c (aangehaal deur num1)
Met behulp van GMP, een kon skryf die volgende:
#include <stdio.h>
#include <gmp.h>
int main() {
mpz_t prime;
mpz_init(prime);
mpz_set_ui(prime, 1);
int i;
char* num = malloc(4000);
for(i=0; i<10000; i++) {
mpz_nextprime(prime, prime);
printf("%s, ", mpz_get_str(NULL,10,prime));
}
}
Op my 2.33 GHz Macbook Pro, dit voer soos volg:
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
Die berekening van 1,000,000 primes op dieselfde laptop:
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP is hoogs geskik vir hierdie soort van ding.Tensy jy regtig wil om te verstaan die algoritmes deur die skryf van jou eie, jy wil word aangeraai om te gebruik libGMP onder C.
Nie doeltreffend op alle, maar jy kan gebruik om'n gereelde uitdrukking te toets vir die eerste getalle.
/^1?$|^(11+?)\1+$/
Hierdie toetse as, vir'n string wat bestaan uit k “1"s, k is nie die eerste (dws.of die string bestaan uit een "1"of enige aantal "1"s wat uitgedruk kan word as'n n-ary produk).
Ek het aangepas kode gevind word op die CodeProject om te skep die volgende:
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
Toets dit op my ASP.NET die Bediener het die rountine sowat 1 minuut om te hardloop.
Hier is'n Sif van Eratosthenes wat ek geskryf het in die PowerShell'n paar dae gelede.Dit het'n parameter vir die identifisering van die aantal van die eerste getalle wat moet teruggestuur word.
#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
param ($target,$count = 0)
$sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
$sieve = @($false) * $sieveBound
$crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
for ($i = 1; $i -le $crossLimit; $i ++) {
if ($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Found: $prime"
for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
$sieve[$x] = $true
}
}
}
$primes = @(2)
for ($i = 1; $i -le $sieveBound; $i ++) {
if($count -gt 0 -and $primes.length -ge $count) {
break;
}
if($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Output: $prime"
$primes += $prime
}
}
return $primes
}
Sif van Eratosthenes is die pad om te gaan, as gevolg van sy eenvoud en spoed.My implementering in C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
int main(void)
{
unsigned int lim, i, j;
printf("Find primes upto: ");
scanf("%d", &lim);
lim += 1;
bool *primes = calloc(lim, sizeof(bool));
unsigned int sqrtlim = sqrt(lim);
for (i = 2; i <= sqrtlim; i++)
if (!primes[i])
for (j = i * i; j < lim; j += i)
primes[j] = true;
printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d\n", i);
return 0;
}
CPU Tyd om uit te vind primes (op Pentium Dual Core E2140 1.6 GHz, met behulp van enkele kern)
~ 4s vir lim = 100,000,000
Die aanpassing van en na aanleiding van GateKiller, hier is die finale weergawe wat ek gebruik het.
public IEnumerable<long> PrimeNumbers(long number)
{
List<long> primes = new List<long>();
for (int i = 2; primes.Count < number; i++)
{
bool divisible = false;
foreach (int num in primes)
{
if (i % num == 0)
divisible = true;
if (num > Math.Sqrt(i))
break;
}
if (divisible == false)
primes.Add(i);
}
return primes;
}
Dit is basies dieselfde, maar ek het bygevoeg dat die "breek op Sqrt" voorstel en verander'n paar van die veranderlikes om te maak dit pas vir my beter.(Ek was besig om op Euler en wat nodig is om die 10001th eerste)
Die Sif blyk te wees die verkeerde antwoord.Die sif gee jou die primes tot 'n aantal N, nie die eerste N primes.Hardloop @Imran of @Andrew Szeto, en jy kry die primes tot N.
Die sif dalk nog bruikbaar as jy aanhou probeer siwwe vir al groter getalle totdat jy getref'n sekere grootte van jou resultaat te stel, en gebruik sommige caching van die nommers wat reeds verkry is, maar ek glo dit sal nog geen vinniger as'n oplossing soos @Pat is.
In Python
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
Die deque sif algoritme genoem deur BenGoldberg verdien'n nader kyk, nie net omdat dit is baie elegant, maar ook omdat dit kan soms nuttig wees in die praktyk (in teenstelling met die Sif van Atkin, wat is'n suiwer akademiese oefening).
Die basiese idee agter die deque sif algoritme is om te gebruik'n klein, gly sif dit is net groot genoeg om te bevat ten minste een aparte verskeie vir elk van die tans aktiewe' eerste faktore - d. w. sdiegene primes wie se vierkante nie meer as die laagste aantal tans verteenwoordig deur die sif beweeg.Nog'n verskil aan die SoE is dat die deque sif winkels die werklike faktore in die gleuwe van samestellings, nie booleans.
Die algoritme strek die grootte van die sif venster as wat nodig is, wat lei tot redelik selfs prestasie oor'n wye verskeidenheid totdat die sif begin oorskry die kapasiteit van die CPU se L1 kas aansienlik.Die laaste eerste wat pas ten volle is 25,237,523 (die 1,579,791 st eerste), wat gee'n rowwe ball figuur vir die redelike bedryfstelsel reeks van die algoritme.
Die algoritme is redelik eenvoudig en sterk, en dit het selfs prestasie oor'n veel wyer omvang as'n unsegmented Sif van Eratosthenes.Laasgenoemde is'n baie vinniger as sy lang sif pas ten volle in die kas, d. w. stot 2^16 vir'n kans-net sif met byte-grootte bools.Dan is sy prestasie druppels meer en meer, maar dit bly altyd aansienlik vinniger as die deque ten spyte van die voorgee (ten minste saamgestel in tale soos C/C++, Pascal of Java/C#).
Hier is'n weergawe van die deque sif algoritme in C#, want ek vind dat taal - ten spyte van sy baie foute - baie meer prakties vir prototyping algoritmes en eksperimentering as die uiters omslagtig en pedanties C++. (Sidenote:Ek is met behulp van die gratis LINQPad wat maak dit moontlik om te duik reg in, sonder al die morsigheid met die opstel van projekte, makefiles, dopgehou of noem maar op, en dit gee my die dieselfde graad van interaktiwiteit as'n python vinnig).
C# hoef nie'n eksplisiete deque tipe, maar die vlakte List<int> werk goed genoeg vir die demonstrasie van die algoritme.
Let daarop:hierdie weergawe maak nie gebruik van'n deque vir die primes, omdat dit eenvoudig nie sin maak nie te pop af sqrt(n) uit n primes.Wat goed dit sou wees om te verwyder 100 primes en te laat 9900?Ten minste op hierdie manier al die primes is versamel in'n netjiese vektor, gereed is vir verdere verwerking.
static List<int> deque_sieve (int n = 10000)
{
Trace.Assert(n >= 3);
var primes = new List<int>() { 2, 3 };
var sieve = new List<int>() { 0, 0, 0 };
for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
{
int base_factor = sieve[0];
if (base_factor != 0)
{
// the sieve base has a non-trivial factor - put that factor back into circulation
mark_next_unmarked_multiple(sieve, base_factor);
}
else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite
{
primes.Add(sieve_base);
if (primes.Count == n)
return primes;
}
else // sieve_base == current_prime_squared
{
// bring the current prime into circulation by injecting it into the sieve ...
mark_next_unmarked_multiple(sieve, primes[current_prime_index]);
// ... and elect a new current prime
current_prime_squared = square(primes[++current_prime_index]);
}
// slide the sieve one step forward
sieve.RemoveAt(0); sieve_base += 2;
}
}
Hier is die twee helper funksies:
static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
int i = prime, e = sieve.Count;
while (i < e && sieve[i] != 0)
i += prime;
for ( ; e <= i; ++e) // no List<>.Resize()...
sieve.Add(0);
sieve[i] = prime;
}
static int square (int n)
{
return n * n;
}
Waarskynlik die maklikste manier van die verstaan van die algoritme is om te dink dat dit as'n spesiale gesegmenteerde Sif van Eratosthenes met'n segment grootte van 1, vergesel deur'n oorloop gebied waar die primes kom om te rus wanneer hulle skiet oor die einde van die segment.Behalwe dat die enkele sel van die segment ('n.k.'n. sieve[0]) het reeds gesif wanneer ons kry om dit, want dit het loop oor terwyl dit was deel van die oorloop gebied.
Die getal wat verteenwoordig word deur sieve[0] is gehou in sieve_base, hoewel sieve_front of window_base sou ook'n goeie name wat toelaat dat parallelle te trek om Ben se kode of implementering van gesegmenteer kan word/met venster siwwe.
As sieve[0] bevat'n nie-nul waarde toe dat waarde is'n faktor van sieve_base, wat kan so word erken as saamgestelde.Aangesien cell 0 is'n veelvoud van daardie faktor dit is maklik om te bereken die volgende hop, wat is eenvoudig 0 plus dat faktor.Moet daardie sel bewoon word reeds deur'n ander faktor dan het ons net die faktor weer, en so aan totdat ons vind'n veelvoud van die faktor waar geen ander faktor is tans geparkeer (die uitbreiding van die sif indien nodig).Dit beteken ook dat daar is geen behoefte vir die berging van die huidige werk skyf van die verskillende primes van een segment na die volgende, soos in'n normale gesegmenteerde sif.Wanneer ons vind'n faktor in die sieve[0], sy huidige werk verreken word 0.
Die huidige eerste kom in die spel in die volgende manier.'n eerste kan raak net die huidige na sy eie voorkoms in die stroom (bv.wanneer dit is waargeneem as'n eerste, want dit is nie gemerk met'n faktor), en dit sal bly huidige tot op die presiese oomblik dat sieve[0] bereik sy vierkante.Al laer veelvoude van hierdie eerste moet getref is af as gevolg van die aktiwiteite van die kleiner primes, net soos in'n gewone SoE.Maar nie een van die kleiner primes kan staking af van die vierkant, aangesien die enigste faktor van die vierkant is die eerste self en dit is nog nie in die verkeer op hierdie punt.Dit verduidelik die aksies wat geneem is deur die algoritme in die geval sieve_base == current_prime_squared (wat impliseer sieve[0] == 0, deur die manier).
Nou die geval is sieve[0] == 0 && sieve_base < current_prime_squared is maklik te verklaar:dit beteken dat sieve_base kan nie'n veelvoud van enige van die primes kleiner as die huidige eerste, of anders sou dit gewees het gemerk as saamgestelde.Ek kan nie'n hoër verskeie van die huidige eerste óf, aangesien sy waarde is minder as die huidige eerste is vierkante.Dus moet dit'n nuwe eerste.
Die algoritme is natuurlik geïnspireer deur die Sif van Eratosthenes, maar ewe duidelik dat dit is baie anders.Die Sif van Eratosthenes ontleen sy beter spoed van die eenvoud van sy basiese bedrywighede:een enkele indeks verder en een winkel vir elke stap van die operasie is al wat dit doen vir'n lang strek van die tyd.
Hier is'n eenvoudige, unsegmented Sif van Eratosthenes wat ek gewoonlik gebruik vir sewe faktor primes in die ushort reeks, d. w. stot 2^16.Vir hierdie post het ek verander dit om te werk as 2^16 deur die vervanging van int vir ushort
static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
}
Wanneer sif die eerste 10000 primes'n tipiese L1 kas van 32 KiByte sal oorskry word nie, maar die funksie is nog steeds baie vinnig (fraksie van'n millisekonde selfs in C#).
As jy vergelyk hierdie kode om die deque sif dan is dit maklik om te sien dat die bedrywighede van die deque sif is'n baie meer ingewikkeld, en dit kan nie effektief amortiseer sy oorhoofse omdat dit nie altyd die kortste moontlike gedeelte van die kruisings-af in'n ry (presies een enkele kruising af, na die draai van al die veelvoude wat gekruis af reeds).
Let daarop:die C# kode gebruik int in plaas van uint want nuwer samestellers het'n gewoonte van die opwekking van substandaard-kode vir uint, waarskynlik in orde te stoot mense na onderteken heelgetalle...In die C++ weergawe van die kode bo ek gebruik unsigned dwarsdeur, natuurlik;die maatstaf het om te wees in C++, want ek wou dit word gebaseer op'n sogenaamde voldoende deque tipe (std::deque<unsigned>;daar was geen prestasie te kry uit die gebruik van unsigned short).Hier is die getalle vir my Haswell laptop (VC++ 2015/x64):
deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms
Let daarop:die C# keer is pretty much presies dubbel die C++ tye, wat is redelik goed vir C# en ìt toon dat List<int> is geen slungelen selfs as misbruik as'n deque.
Die eenvoudige sif kode nog steeds waai die deque uit die water, selfs al is dit is reeds aktief buite die normale omvang (L1 kas grootte oorskry deur 50%, met gepaardgaande kas loesing).Die oorheersende deel hier is die lees van die gesif primes, en dit is nie geraak nie veel deur die kas probleem.In elk geval is die funksie is ontwerp vir sewe die faktore van faktore, bv.vlak 0 in'n 3-vlak sif hiërargie, en gewoonlik is dit het om terug te keer slegs'n paar honderd faktore of'n lae aantal van die duisende.Vandaar sy eenvoud.
Prestasie kan verbeter word deur meer as'n orde van grootte deur die gebruik van'n gesegmenteerde sif en die optimalisering van die kode vir die wen van die gesif primes (trap mod 3 en oopgerol twee keer, of mod 15 en oopgerol keer) , en nog meer prestasie kan wees benoud uit van die kode deur die gebruik van'n mod 16 of mod 30 wiel met al die versierings (d. w. svolle unrolling vir al die oorblyfsels).Iets soos dit verduidelik is in my antwoord aan Vind die eerste geposisioneer eerste nommer oor die op-Kode Hersiening, waar'n soortgelyke probleem is bespreek.Maar dit is moeilik om te sien die punt in die verbetering van sub-millisekonde keer vir'n een-off taak...
Om dinge'n bietjie in perspektief te stel, hier is die C++ tye vir sewe tot 100,000,000:
deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms
In teenstelling, 'n gesegmenteerde sif in C# met'n paar klokkies en fluitjies doen dieselfde werk in 95 ms (geen C++ tye beskikbaar is nie, aangesien ek doen kode uitdagings slegs in C# op die oomblik).
Dinge kan kyk beslis anders in'n geïnterpreteer taal soos Python waar elke operasie het'n swaar koste en die tolk oorhoofse dwerge al die verskille as gevolg van te voorspel vs.mispredicted takke of sub-siklus ops (skuif, benewens) vs.multi-siklus ops (vermenigvuldiging, en miskien selfs die afdeling).Wat is gebind om te erodeer die eenvoud voordeel van die Sif van Eratosthenes, en dit kan maak die deque oplossing'n bietjie meer aantreklik te maak.
Ook, baie van die tye wat deur ander respondente in hierdie onderwerp is waarskynlik oorheers deur uitset tyd.Dit is'n heeltemal ander oorlog, waar my vernaamste wapen is'n eenvoudige klas soos hierdie:
class CCWriter
{
const int SPACE_RESERVE = 11; // UInt31 + '\n'
public static System.IO.Stream BaseStream;
static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range
static int m_write_pos = 0;
public static long BytesWritten = 0; // for statistics
internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();
internal static ushort[] create_double_digit_lookup ()
{
var lookup = new ushort[100];
for (int lo = 0; lo < 10; ++lo)
for (int hi = 0; hi < 10; ++hi)
lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);
return lookup;
}
public static void Flush ()
{
if (BaseStream != null && m_write_pos > 0)
BaseStream.Write(m_buffer, 0, m_write_pos);
BytesWritten += m_write_pos;
m_write_pos = 0;
}
public static void WriteLine ()
{
if (m_buffer.Length - m_write_pos < 1)
Flush();
m_buffer[m_write_pos++] = (byte)'\n';
}
public static void WriteLinesSorted (int[] values, int count)
{
int digits = 1, max_value = 9;
for (int i = 0; i < count; ++i)
{
int x = values[i];
if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
Flush();
while (x > max_value)
if (++digits < 10)
max_value = max_value * 10 + 9;
else
max_value = int.MaxValue;
int n = x, p = m_write_pos + digits, e = p + 1;
m_buffer[p] = (byte)'\n';
while (n >= 10)
{
int q = n / 100, w = m_double_digit_lookup[n - q * 100];
n = q;
m_buffer[--p] = (byte)w;
m_buffer[--p] = (byte)(w >> 8);
}
if (n != 0 || x == 0)
m_buffer[--p] = (byte)((byte)'0' + n);
m_write_pos = e;
}
}
}
Dit neem minder as 1 ms vir die skryf van 10000 (gesorteer) getalle.Dit is'n statiese die klas, want dit is bedoel vir die tekstuele insluiting in die kodering uitdaging voorleggings, met'n minimum van ophef en'n nul oorhoofse.
In die algemeen, ek het dit gevind word baie vinniger as gefokusde werk is gedoen op die hele groepe, wat beteken sif'n sekere afstand, dan onttrek al die primes in'n vektor/skikking, dan stoot uit die hele skikking, dan sif die volgende reeks en so aan, in plaas van vermenging alles saam.Met afsonderlike funksies gefokus op spesifieke take ook maak dit makliker om te meng en pas, is dit in staat stel hergebruik, en dit vergemaklik ontwikkeling/toets.
Hier is my VB 2008 kode, wat vind al die primes <10,000,000 in 1 min 27 sekondes op my laptop werk.Dit spring selfs getalle en net lyk vir primes wat < die sqrt van die toets nommer.Dit is net ontwerp om te vind primes van 0 tot'n sentinal waarde.
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles
Button1.Click
Dim TestNum As Integer
Dim X As Integer
Dim Z As Integer
Dim TM As Single
Dim TS As Single
Dim TMS As Single
Dim UnPrime As Boolean
Dim Sentinal As Integer
Button1.Text = "Thinking"
Button1.Refresh()
Sentinal = Val(SentinalTxt.Text)
UnPrime = True
Primes(0) = 2
Primes(1) = 3
Z = 1
TM = TimeOfDay.Minute
TS = TimeOfDay.Second
TMS = TimeOfDay.Millisecond
For TestNum = 5 To Sentinal Step 2
Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
UnPrime = False
End If
X = X + 1
Loop
If UnPrime = True Then
X = X + 1
Z = Z + 1
Primes(Z) = TestNum
End If
UnPrime = True
X = 0
Next
Button1.Text = "Finished with " & Z
TM = TimeOfDay.Minute - TM
TS = TimeOfDay.Second - TS
TMS = TimeOfDay.Millisecond - TMS
ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
Die volgende Mathcad kode bereken die eerste miljoen primes in minder as 3 minute.
Hou in gedagte dat dit sou wees om met behulp van swaai punt verdubbel vir al die nommers en is basies vertolk.Ek hoop die sintaksis is duidelik.
Hier is'n C++ oplossing, met behulp van'n vorm van Sbo:
#include <iostream>
#include <deque>
typedef std::deque<int> mydeque;
void my_insert( mydeque & factors, int factor ) {
int where = factor, count = factors.size();
while( where < count && factors[where] ) where += factor;
if( where >= count ) factors.resize( where + 1 );
factors[ where ] = factor;
}
int main() {
mydeque primes;
mydeque factors;
int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
int cnt = 2;
factors.resize(3);
std::cout << "2 3 ";
while( cnt < 10000 ) {
int factor = factors.front();
maybe_prime += 2;
if( factor ) {
my_insert( factors, factor );
} else if( maybe_prime < a_square_prime ) {
std::cout << maybe_prime << " ";
primes.push_back( maybe_prime );
++cnt;
} else {
my_insert( factors, a_prime );
a_prime = primes.front();
primes.pop_front();
a_square_prime = a_prime * a_prime;
}
factors.pop_front();
}
std::cout << std::endl;
return 0;
}
Let daarop dat hierdie weergawe van die Sif kan bereken primes onbepaald.
Let ook op, die STL deque neem O(1) tyd uit te voer push_back, pop_front, en ewekansige toegang tot al subscripting.
Die resize die operasie neem O(n) tyd, waar n is die aantal van die elemente bygevoeg.As gevolg van hoe ons is met behulp van hierdie funksie, kan ons behandel hierdie is'n klein konstante.
Die liggaam van die while lus in my_insert is uitgevoer O(log log n) tye, waar n is gelyk aan die veranderlike maybe_prime.Dit is omdat die toestand uitdrukking van die while sal evalueer om te ware een keer vir elke eerste faktor van maybe_prime.Sien "Deler funksie"op Wikipedia.
Vermenigvuldig deur die aantal van die tye my_insert genoem word, toon dat dit moet neem O(n log log n) tyd om te lys n primes...wat is, verrassend, die tyd, die kompleksiteit van wat die Sif van Eratosthenes veronderstel is om te hê.
Egter, terwyl hierdie kode is doeltreffende, dit is nie die mees doeltreffende...Ek sou raai die gebruik van'n gespesialiseerde biblioteek vir primes generasie, so as primesieve.Enige werklik doeltreffende, goed optimale oplossing is, sal meer kode as iemand wil om te tik in Stackoverflow.
Met behulp van'n Sif van Eratosthenes, berekening is baie vinniger vergelyk met "bekend-wye" eerste getalle algoritme.
Deur gebruik te maak van pseudokode van it se wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), Het ek in staat wees om die oplossing op C#.
/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
if (n <= 1) {
return new int[] { };
}
var mark = new bool[n];
for(var i = 2; i < n; i++) {
mark[i] = true;
}
for (var i = 2; i < Math.Sqrt(n); i++) {
if (mark[i]) {
for (var j = (i * i); j < n; j += i) {
mark[j] = false;
}
}
}
var primes = new List<int>();
for(var i = 3; i < n; i++) {
if (mark[i]) {
primes.Add(i);
}
}
return primes.ToArray();
}
GetPrimes(100000000) neem 2s en 330ms.
NOTA:Waarde kan wissel, afhanklik van die Hardeware Spesifikasies.
Ek spandeer'n geruime tyd die skryf van'n program vir die berekening van'n baie van die primes en dit is die kode wat ek gebruik om te bereken'n teks lêer met die eerste 1.000.000.000 primes.Dit is in duits, maar die interessante deel is die metode calcPrimes().Die primes gestoor word in'n skikking genoem Primzahlen.Ek beveel'n 64bit CPU omdat die berekeninge is met 64bit heelgetalle.
import java.io.*;
class Primzahlengenerator {
long[] Primzahlen;
int LastUnknown = 2;
public static void main(String[] args) {
Primzahlengenerator Generator = new Primzahlengenerator();
switch(args.length) {
case 0: //Wenn keine Argumente übergeben worden:
Generator.printHelp(); //Hilfe ausgeben
return; //Durchfallen verhindern
case 1:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//dutchfallen verhindern
case 2:
switch (args[1]) {
case "-l":
System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//durchfallen verhindern
case 3:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
switch(args[1]) {
case "-l":
Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
break;
default:
Generator.printHelp();
break;
}
break;
default:
Generator.printHelp();
return;
}
Generator.calcPrims();
}
void printHelp() {
System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss
System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
}
void loadFromFile(String File) {
// System.out.println("Lese Datei namens: \"" + File + "\"");
try{
int x = 0;
BufferedReader in = new BufferedReader(new FileReader(File));
String line;
while((line = in.readLine()) != null) {
Primzahlen[x] = new Long(line).longValue();
x++;
}
LastUnknown = x;
} catch(FileNotFoundException ex) {
System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
} catch(IOException ex) {
System.err.println(ex);
} catch(ArrayIndexOutOfBoundsException ex) {
System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
}
/* for(long prim : Primzahlen) {
System.out.println("" + prim);
} */
//Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
//java Primzahlengenerator 1000 > 1000Primzahlen.txt
//da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
//erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
//falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
//int[] foo = { 1, 2, 3};
//int bar = foo[4];
//dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
}
void calcPrims() {
int PrimzahlNummer = LastUnknown;
// System.out.println("LAstUnknown ist: " + LastUnknown);
Primzahlen[0] = 2;
Primzahlen[1] = 3;
long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
boolean IstPrimzahl;
// System.out.println("2");
// System.out.println("3");
int Limit = Primzahlen.length;
while(PrimzahlNummer < Limit) {
IstPrimzahl = true;
double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
for(int i = 1;i < PrimzahlNummer;i++) {
if(AktuelleZahl % Primzahlen[i] == 0) {
IstPrimzahl = false;
break;
}
if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
}
if(IstPrimzahl) {
Primzahlen[PrimzahlNummer] = AktuelleZahl;
PrimzahlNummer++;
// System.out.println("" + AktuelleZahl);
}
AktuelleZahl = AktuelleZahl + 2;
}
for(long prim : Primzahlen) {
System.out.println("" + prim);
}
}
}
Ek geskryf het, dit met behulp van python, as ek net begin leer om dit, en dit werk perfek goed.Die 10,000 de eerste genereer deur hierdie kode as dieselfde as wat in http://primes.utm.edu/lists/small/10000.txt.Om te kyk as n is eerste of nie, verdeel n deur die nommers van 2 om te sqrt(n).Indien enige van hierdie omvang van die aantal perfek verdeel n dan is dit nie die eerste.
import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):
e = c % b
e = int(e)
if (e == 0):
x = x+1
if (x == 0):
print("%d is prime number" % c)
count = count + 1
print("Total number of prime till %d is %d" % (a,count))
Ek het al die werk op die vind primes vir sowat'n jaar.Dit is wat ek gevind het om te wees die vinnigste:
import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
public static void main(String[] args) {
primelist primes = new primelist();
primes.insert(3);
primes.insert(5);
File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
file.getParentFile().mkdirs();
long time = System.nanoTime();
try{
PrintWriter printWriter = new PrintWriter ("file0024.txt");
int linenum = 0;
printWriter.print("2");
printWriter.print (" , ");
printWriter.print("3");
printWriter.print (" , ");
int up;
int down;
for(int i =1; i<357913941;i++){//
if(linenum%10000==0){
printWriter.println ("");
linenum++;
}
down = i*6-1;
if(primes.check(down)){
primes.insert(down);
//System.out.println(i*6-1);
printWriter.print ( down );
printWriter.print (" , ");
linenum++;
}
up = i*6+1;
if(primes.check(up)){
primes.insert(up);
//System.out.println(i*6+1);
printWriter.print ( up );
printWriter.print (" , ");
linenum++;
}
}
printWriter.println ("Time to execute");
printWriter.println (System.nanoTime()-time);
//System.out.println(primes.length);
printWriter.close ();
}catch(Exception e){}
}
}
class node{
node next;
int x;
public node (){
node next;
x = 3;
}
public node(int z) {
node next;
x = z;
}
}
class primelist{
node first;
int length =0;
node current;
public void insert(int x){
node y = new node(x);
if(current == null){
current = y;
first = y;
}else{
current.next = y;
current = y;
}
length++;
}
public boolean check(int x){
int p = (int)sqrt(x);
node y = first;
for(int i = 0;i<length;i++){
if(y.x>p){
return true;
}else if(x%y.x ==0){
return false;
}
y = y.next;
}
return true;
}
}
1902465190909 nano sekondes om te kry om 2147483629 begin by 2.
Hier is my kode wat vind
eerste 10,000 primes in 0.049655 sec op my laptop, eerste 1,000,000 primes in onder 6 sekondes en die eerste 2,000,000 in 15 sekondes
'n bietjie verduideliking.Hierdie metode maak gebruik van 2 tegnieke om uit te vind die eerste nommer
- eerste van alles enige nie-die eerste nommer is'n samestelling van veelvoude van priemgetalle so hierdie kode toets deur die verdeling van die toets aantal deur kleiner eerste nommers in plaas van'n nommer, dit verminder die berekening deur ten minste 10 keer vir'n 4-syfer getal en selfs meer vir'n groter aantal
- tweedens behalwe die verdeling deur die eerste, is dit net verdeel deur die eerste getalle wat kleiner of gelyk aan die wortel van die aantal getoets verdere vermindering van die berekeninge aansienlik, hierdie werk, want enige getal wat groter is as die wortel van die getal sal'n eweknie getal wat het om te wees kleiner as die wortel van die aantal maar aangesien ons getoets het al die getalle kleiner as die wortel reeds, Daarom het ons nie nodig om te pla met'n getal groter as die wortel van die aantal getoets.
Voorbeeld van afvoer vir die eerste 10,000 eerste nommer
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
Hier is die kode in C-taal,
Tik 1 en dan 10,000 om uit te druk van die eerste 10,000 primes.
Edit:Ek het vergeet dit bevat wiskunde biblioteek ,as jy op windows of visual studio as dit moet goed wees, maar op linux jy moet stel om die kode te gebruik -lm argument of die kode kan nie werk nie
Voorbeeld:gcc -Wall -o "%e" "%f" -lm
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
/* Finding prime numbers */
int main()
{
//pre-phase
char d,w;
int l,o;
printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o
printf(" Enter 1 or 2 to get anwser of first or second question\n");
// decision making
do
{
printf(" -->");
scanf("%c",&d);
while ((w=getchar()) != '\n' && w != EOF);
if ( d == '1')
{
printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->");
scanf("%10d",&l);
o=INT_MAX;
printf(" Here we go!\n\n");
break;
}
else if ( d == '2' )
{
printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->");
scanf("%10d",&o);
l=o/log(o)*1.25;
printf(" Here we go!\n\n");
break;
}
else printf("\n Try again\n");
}while ( d != '1' || d != '2' );
clock_t start, end;
double cpu_time_used;
start = clock(); /* starting the clock for time keeping */
// main program starts here
int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
int s,x;
int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
p[1]=2;
p[2]=3;
p[3]=5;
printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
p[i]=0;
n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */
/* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */
// the main loop begins here
for ( m=4,j=1,c=2; m<=l && n <= o;)
/* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
{
// this will divide n by prime number in p[j] and tries to rule out non-primes
if ( n%p[j]==0 )
{
/* these steps execute if the number n is found to be non-prime */
++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
{
x=p[c];
++c;
}
j=1;
/* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop for the new cycle */
}
// confirmation test for the prime number candidate n
else if ( n%p[j]!=0 && p[j]==x )
{
/* these steps execute if the number is found to be prime */
p[m]=n;
printf("%10dth:%10d\n",m,p[m]);
++n;
s = sqrt(n);
++m;
j=1;
/* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop */
/* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
}
++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
// if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
// and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
}
// the loops ends
printf(" All done !!\n");
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf(" Time taken : %lf sec\n",cpu_time_used);
}
Hier is die kode wat ek gemaak het :
enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/
unsigned long int n;
int prime(unsigned long int);
scanf("%ld",&n);
unsigned long int val;
for(unsigned long int i=0;i<n;i++)
{
int flag=0;
scanf("%ld",&val);
flag=prime(val);
if(flag==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
int prime(unsigned long int n)
{
if(n==2) return 1;
else if (n == 1||n%2==0) return 0;
for (unsigned long int i=3; i<=sqrt(n); i+=2)
if (n%i == 0)
return 0;
return 1;
}
Met behulp van die Skikking.prototipe.vind() metode in Javascript.2214.486 ms
function isPrime (number) {
function prime(element) {
let start = 2;
while (start <= Math.sqrt(element)) {
if (element % start++ < 1) {
return false;
}
}
return element > 1;
}
return [number].find(prime)
}
function logPrimes (n) {
let count = 0
let nth = n
let i = 0
while (count < nth) {
if (isPrime(i)) {
count++
console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
if (count === nth) {
console.log('while i', i)
console.log('count', count)
}
}
i++
}
}
console.time(logPrimes)
logPrimes(10000)
console.timeEnd(logPrimes) // 2214.486ms
Ek kan gee jou'n paar wenke, jy het om dit te implementeer.
- Vir elke nommer, kry die helfte van daardie getal.E. g.vir die beheer van 21, net kry die res deur die verdeling dit uit wissel 2-10.
- As sy'n onewe getal, slegs verdeel deur onewe getal, en omgekeerd.Soos vir 21, verdeel met 3, 5, 7, 9 net.
Die mees doeltreffende metode wat ek gekry het tot so ver.
Omdat jy wil hê eerste 10000 primes net, eerder as kodering komplekse algoritme ek sal stel die volgende
boolean isPrime(int n){
//even but is prime
if(n==2)
return true;
//even numbers filtered already
if(n==0 || n==1 || n%2==0)
return false;
// loop for checking only odd factors
// i*i <= n (same as i<=sqrt(n), avoiding floating point calculations)
for(int i=3 ; i*i <=n ; i+=2){
// if any odd factor divides n then its not a prime!
if(n%i==0)
return false;
}
// its prime now
return true;
}
nou noem is eerste as jy dit nodig het
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer: ");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First " + n + " Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
}
