Deze c++-code drukt de volgende priemgetallen af: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97.
Maar ik denk niet dat mijn boek zo wil dat het geschreven wordt. Het vermeldt iets over de vierkantswortel van een getal. Dus ik heb geprobeerd mijn 2e lus te veranderen in for (int j=2; j<sqrt(i); j++)maar het gaf me niet het resultaat dat ik nodig had.
Hoe moet ik deze code veranderen in de manier waarop mijn boek het wil hebben?
int main ()
{
for (int i=2; i<100; i++)
for (int j=2; j<i; j++)
{
if (i % j == 0)
break;
else if (i == j+1)
cout << i << " ";
}
return 0;
}
Een priemgetal is een getal met
precies twee verschillende delers,
namelijk 1 en het nummer zelf. Schrijven,
voer en test een C++-programma dat
vindt en print alle priemgetallen
minder dan 100. (Hint: 1 is een priemgetal
nummer. Voor elk nummer van 2 tot 100,
zoek Rest = Getal % n, waarbij n
varieert van 2 tot sqrt(getal). \ Indien n
groter is dan sqrt(getal), the
getal is niet gelijk deelbaar door n.
Waarom? Als een Rest gelijk is aan 0, is de
getal is geen priemgetal.)
Antwoord 1, autoriteit 100%
Drie manieren:
1.
int main ()
{
for (int i=2; i<100; i++)
for (int j=2; j*j<=i; j++)
{
if (i % j == 0)
break;
else if (j+1 > sqrt(i)) {
cout << i << " ";
}
}
return 0;
}
2.
int main ()
{
for (int i=2; i<100; i++)
{
bool prime=true;
for (int j=2; j*j<=i; j++)
{
if (i % j == 0)
{
prime=false;
break;
}
}
if(prime) cout << i << " ";
}
return 0;
}
3.
#include <vector>
int main()
{
std::vector<int> primes;
primes.push_back(2);
for(int i=3; i < 100; i++)
{
bool prime=true;
for(int j=0;j<primes.size() && primes[j]*primes[j] <= i;j++)
{
if(i % primes[j] == 0)
{
prime=false;
break;
}
}
if(prime)
{
primes.push_back(i);
cout << i << " ";
}
}
return 0;
}
Bewerken: in het derde voorbeeld houden we al onze eerder berekende priemgetallen bij. Als een getal deelbaar is door een niet-priemgetal, is er ook een priemgetal <= die deler waardoor het ook deelbaar is. Dit vermindert de berekening met een factor primes_in_range/total_range.
Antwoord 2, autoriteit 52%
Als jgelijkis aan sqrt(i)kan het ook een geldige factor zijn, niet alleen als het kleiner.
Om tot en met sqrt(i)in je inner loop te herhalen, zou je kunnen schrijven:
for (int j=2; j*j<=i; j++)
(Vergeleken met het gebruik van sqrt(i)heeft dit het voordeel dat er geen conversie naar getallen met drijvende komma nodig is.)
Antwoord 3, autoriteit 36%
Als een getal delers heeft, moet minstens één daarvan kleiner zijn dan of gelijk zijn aan de vierkantswortel van het getal. Wanneer u delers controleert, hoeft u alleen tot aan de vierkantswortel te controleren, niet helemaal tot aan het getal dat wordt getest.
Antwoord 4, autoriteit 21%
Dit is mijn zeer eenvoudige c++-programma om de priemgetallen tussen 2 en 100 op te sommen.
for(int j=2;j<=100;++j)
{
int i=2;
for(;i<=j-1;i++)
{
if(j%i == 0)
break;
}
if(i==j && i != 2)
cout<<j<<endl;
}
Antwoord 5, autoriteit 15%
Met behulp van Sieve of Eratosthenes-logica kan ik dezelfde resultaten bereiken met veel hogeresnelheid.
Mijn codedemoVS antwoord geaccepteerd.
De countvergelijken,
mijn code heeft aanzienlijk minder iteratie nodig om de klus te klaren. Bekijk uiteindelijk de resultaten voor verschillende N-waarden.
Waarom deze code beter presteert dan de reeds geaccepteerde:
– de even getallen worden tijdens het proces niet één keer gecontroleerd.
– zowel binnen- als buitenlussen controleren alleen binnen mogelijke limieten. Geen externe controles.
Code:
int N = 1000; //Print primes number from 1 to N
vector<bool> primes(N, true);
for(int i = 3; i*i < N; i += 2){ //Jump of 2
for(int j = 3; j*i < N; j+=2){ //Again, jump of 2
primes[j*i] = false;
}
}
if(N >= 2) cout << "2 ";
for(int i = 3; i < N; i+=2){ //Again, jump of 2
if(primes[i] == true) cout << i << " ";
}
Voor N = 1000duurt mijn code 1166 herhalingen, het geaccepteerde antwoord duurt 5287 (4,5 keer langzamer)
Voor N = 10000duurt mijn code 14637 herhalingen, het geaccepteerde antwoord duurt 117526 (8 keer langzamer)
Voor N = 100000duurt mijn code 175491 iteraties, het geaccepteerde antwoord duurt 2745693 (15,6 keer langzamer)
Antwoord 6, autoriteit 12%
eigenlijk is de betere oplossing om “Een priemzeef of priemgetalzeef” te gebruiken, wat “een snel type algoritme is voor het vinden van priemgetallen” .. wikipedia
Het eenvoudige (maar niet snellere) algoritme wordt “zeef van eratosthenes” genoemd en kan in de volgende stappen worden gedaan (opnieuw van wikipedia):
- Maak een lijst met opeenvolgende gehele getallen van 2 tot n: (2, 3, 4, …, n).
- Laat p aanvankelijk gelijk zijn aan 2, het eerste priemgetal.
- Vanaf p, tel op in stappen van p en markeer elk van deze getallen groter dan p zelf in de lijst. Deze nummers worden
2p, 3p, 4p, enz.; merk op dat sommige ervan mogelijk al zijn gemarkeerd.- Zoek het eerste getal groter dan p in de lijst dat niet is gemarkeerd. Als er geen dergelijk nummer was, stop dan. Anders, laat p nu gelijk zijn aan
dit getal (dat het volgende priemgetal is), en herhaal vanaf stap 3.
Antwoord 7, autoriteit 9%
Het vinden van priemgetallen tot 100is vooral leuk en gemakkelijk:
printf("2 3 "); // first two primes are 2 and 3
int m5 = 25, m7 = 49, i = 5, d = 4;
for( ; i < 25; i += (d=6-d) )
{
printf("%d ", i); // all 6-coprimes below 5*5 are prime
}
for( ; i < 49; i += (d=6-d) )
{
if( i != m5) printf("%d ", i);
if( m5 <= i ) m5 += 10; // no multiples of 5 below 7*7 allowed!
}
for( ; i < 100; i += (d=6-d) ) // from 49 to 100,
{
if( i != m5 && i != m7) printf("%d ", i);
if( m5 <= i ) m5 += 10; // sieve by multiples of 5,
if( m7 <= i ) m7 += 14; // and 7, too
}
De vierkantswortel van 100is 10, dus deze weergave van de zeef van Eratosthenesmet de 2-3wielgebruikt de veelvouden van alleen de priemgetallen boven 3die niet groter zijn dan 10— namelijk. Alleen 5en 7! — om de 6-coprimes onder 100stapsgewijs te zeven.
Antwoord 8, autoriteit 6%
Het is prima om je for-lus te veranderen in for (int j=2; j<=sqrt(i); j++)maar dan moet je ook nog iets anders veranderen. Als u specifiek kijkt naar uw afdrukconditie,
else if (i == j+1) {
cout << i << " ";
}
waarom wordt dat nooit geactiveerd als u slechts tot sqrt(i)herhaalt? Waar kun je de coutnaartoe verplaatsen om dit te wijzigen? (Hint: misschien wilt u de afdruk uit de lus halen en dan een of ander type vlagvariabele gebruiken)
Antwoord 9, autoriteit 6%
Ik controleer of een getal een priemgetal is of niet met de volgende code (natuurlijk met behulp van sqrt):
bool IsPrime(const unsigned int x)
{
const unsigned int TOP
= static_cast<int>(
std::sqrt( static_cast<double>( x ) )
) + 1;
for ( int i=2; i != TOP; ++i )
{
if (x % i == 0) return false;
}
return true;
}
Ik gebruik deze methode om de priemgetallen te bepalen:
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <cmath>
void initialize( unsigned int *, const unsigned int );
void show_list( const unsigned int *, const unsigned int );
void criba( unsigned int *, const unsigned int );
void setItem ( unsigned int *, const unsigned int, const unsigned int );
bool IsPrime(const unsigned int x)
{
const unsigned int TOP
= static_cast<int>(
std::sqrt( static_cast<double>( x ) )
) + 1;
for ( int i=2; i != TOP; ++i )
{
if (x % i == 0) return false;
}
return true;
}
int main()
{
unsigned int *l;
unsigned int n;
cout << "Ingrese tope de criba" << endl;
cin >> n;
l = new unsigned int[n];
initialize( l, n );
cout << "Esta es la lista" << endl;
show_list( l, n );
criba( l, n );
cout << "Estos son los primos" << endl;
show_list( l, n );
}
void initialize( unsigned int *l, const unsigned int n)
{
for( int i = 0; i < n - 1; i++ )
*( l + i ) = i + 2;
}
void show_list( const unsigned int *l, const unsigned int n)
{
for( int i = 0; i < n - 1; i++ )
{
if( *( l + i ) != 0)
cout << l[i] << " - ";
}
cout << endl;
}
void setItem( unsigned int *l, const unsigned int n, const unsigned int p)
{
unsigned int i = 2;
while( p * i <= n)
{
*( l + (i * p - 2) ) = 0;
i++;
}
}
void criba( unsigned int *l, const unsigned int n)
{
for( int i = 0; i * i <= n ; i++ )
if( IsPrime ( *( l + i) ) )
setItem( l, n, *(l + i) );
}
Antwoord 10, autoriteit 3%
Het boek lijkt “C++ for Engineers and Scientists” te zijn
geschreven door Gary Bronson (gegoogled).
Is dit een mogelijk antwoord? IMHO het is verrassend.
Ik moest de vraag (uit het boek) een paar keer lezen.
Mijn interpretatie:
Voor elkgetal N: 2 <= N < 100 controleer of het een priemgetal is.
Hoe? Voor elkedeler D: 2 <= D < sqrt(N) ,
als D N deelt, is N geen priemgetal,
als D > sqrt(N), N is priemgetal.
Probeer het eens:
N = 2, sqrt(2) ≈ 1.41, D = 2, 2 < 1.41 ? no 2 > 1.41 ? yes 2 is prime.
N = 3, sqrt(3) ≈ 1.73, D = 2, 2 < 1.73 ? no 2 > 1.73 ? yes 3 is prime.
N = 4, sqrt(4) = 2.00, D = 2, 2 < 2.00 ? no 2 > 2.00 ? no 4 is not prime.
N = 5, sqrt(5) ≈ 2.24, D = 2, 2 < 2.24 ? yes 5 % 2 > 0? yes
D = 3, 3 < 2.24 ? no 3 > 2.24 ? yes 5 is prime.
N = 6, sqrt(6) ≈ 2.45, D = 2, 2 < 2.45 ? yes 6 % 2 = 0 2 > 2.45 ? no 6 is not prime.
Voor zover ik kan zien, moeten de priemgetallen zo worden gevonden,
niet met een zeef (veel, veel sneller),
maar met: het antwoord zit in de vraag!Verrassend?
Snelheid? priemgetallen < 400.000: minder dan 10 seconden (op mijn horloge, een rolex, ik kocht hem op de markt, de verkoper zei dat het een echte was, een echte voor de prijs van twee baguettes, ook met 12 echte diamanten).
Laten we de priemgetallen tellen (ik ga geen code tonen 😉 :
664579 priemgetallen < 10.000.000: 5 seconden.
#include "stdafx.h"
#include <math.h>
#include <iostream>
using namespace std;
int main()
{
double rt;
for (int d = 2, n = 2; n < 100; d = 2, n++)
{
for (rt = sqrt(n); d < rt; d++)
if (n % d == 0) break;
if (d > rt) cout << n << " ";
}
getchar(); // 25 primes :-)
}
Verwijderde een eerder antwoord met (zoals andere antwoorden) een prime-zeef.
Hopelijk krijg ik snel mijn volgende “Necromancer” -badge.
Ik heb de auteur gevraagd: in uw boek: “C++ voor E & AMP; S”
is een oefening over prime-nummers, [XRCS] … [/ XRCS].
Zeven jaar geleden werd het gevraagd om: SO / Q / 5200879
Een paar dagen geleden gaf ik een antwoord: SO / A / 49199435
Denk je dat het een redelijke oplossing is, of misschien wel de oplossing.
Hij antwoordde: Peter, ik heb nooit echt een specifieke oplossing in gedachten
Als ik de oefeningen verzonnen,
Dus ik kan niet zeggen dat ik je exacte oplossing in gedachten had.
De vreugde van C++ is dat men echt creatieve oplossingen en geweldige code kan bedenken,
Zoals, op het eerste gezicht, het lijkt erop dat je het gedaan hebt.
Bedankt voor het verzenden van het!
Dr. Bronson
Ik ging naar https://youtu.be/1175AXY2vvw
PS. Een zeef: https://pastebin.com/jmdtxbej
Antwoord 11
Het gebruik van de regels van deelname van deelbaarheid is te vinden in O (n) en het is echt effecient Regels van deelbaarheid
De oplossing zou gebaseerd zijn op de individuele cijfers van het nummer …
Antwoord 12
#include<iostream>
using namespace std;
void main()
{
int num,i,j,prime;
cout<<"Enter the upper limit :";
cin>>num;
cout<<"Prime numbers till "<<num<<" are :2, ";
for(i=3;i<=num;i++)
{
prime=1;
for(j=2;j<i;j++)
{
if(i%j==0)
{
prime=0;
break;
}
}
if(prime==1)
cout<<i<<", ";
}
}
Antwoord 13
Hier is mijn implementatie van Sieve of Eratosthenes (voor priemgetallen tussen 2 & n)
#include <iostream>
int main (){
int n=0;
std::cout << "n = ";
std::cin >> n;
std::cout << std::endl;
if (n==0 || n==1){
std::cout << "No primes in this range" << std::endl;
return 0;
}
const int array_len = n-2+1;
int the_int_array[array_len];
for (int counter=2; counter <=n; counter++)
the_int_array[counter-2]=counter;
int runner = 0;
int new_runner = 0;
while (runner < array_len ){
if (the_int_array[runner]!=0){
new_runner = runner;
new_runner = new_runner + the_int_array[runner];
while (new_runner < array_len){
the_int_array[new_runner] = 0;
new_runner = (new_runner + the_int_array[runner]);
}
}
runner++;
}
runner = 0;
while (runner < array_len ){
if (the_int_array[runner]!=0)
std::cout << the_int_array[runner] << " ";
runner++;
}
std::cout << std::endl;
return 0;
}
Antwoord 14
#include "stdafx.h"
#include<iostream>
using namespace std;
void main()
{ int f =0;
for(int i=2;i<=100;i++)
{
f=0;
for(int j=2;j<=i/2;j++)
{
if(i%j==0)
{ f=1;
break;
}
}
if (f==0)
cout<<i<<" ";
}
system("pause");
}
Antwoord 15
dit is mijn benadering van een eenvoudige blog:
//Prime Numbers generation in C++
//Using for loops and conditional structures
#include <iostream>
using namespace std;
int main()
{
int a = 2; //start from 2
long long int b = 1000; //ends at 1000
for (int i = a; i <= b; i++)
{
for (int j = 2; j <= i; j++)
{
if (!(i%j)&&(i!=j)) //Condition for not prime
{
break;
}
if (j==i) //condition for Prime Numbers
{
cout << i << endl;
}
}
}
}
– Zie meer op: http:// www.programmingtunes.com/generation-of-prime-numbers-c/#sthash.YoWHqYcm.dpuf
Antwoord 16
Om te zien of nee. is priem of niet C++:
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n, counter=0;
cout <<"Enter a number to check whether it is prime or not \n";
cin>>n;
for(int i=2; i<=n-1;i++) {
if (n%i==0) {
cout<<n<<" is NOT a prime number \n";
break;
}
counter++;
}
//cout<<"Value n is "<<n<<endl;
//cout << "number of times counter run is "<<counter << endl;
if (counter == n-2)
cout << n<< " is prime \n";
return 0;
}
Antwoord 17
Ik deed het in Perl op basis van het populairste antwoord van de 2e methode van Prodigysim. Ik moest een breakequivalent in Perl, last, direct na de print $i . " \n";om te voorkomen dat de primes twee keer wordt uitgevoerd.
#!/bin/perl
use strict;
for(my $i=2; $i < 100; $i++){
my $prime = 1;
for (my $j=2; $j*$j<=$i; $j++){
if ($i % $j == 0){
$prime = 0;
last;
}
if($prime) {
print $i . " \n";
last;
}
}
}
Antwoord 18
Een eenvoudig programma om “N” Prime-nummers af te drukken. U kunt N-waarde gebruiken als 100.
#include <iostream >
using namespace std;
int main()
{
int N;
cin >> N;
for (int i = 2; N > 0; ++i)
{
bool isPrime = true ;
for (int j = 2; j < i; ++j)
{
if (i % j == 0)
{
isPrime = false ;
break ;
}
}
if (isPrime)
{
--N;
cout << i << "\n";
}
}
return 0;
}
Antwoord 19
Hier is een eenvoudige code voor het afdrukken van alle prime-nummers tot het gegeven nummer n,
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int n,i,j,k;
cout<<"Enter n\n";
cin>>n;
for(i=1;i<=n;i++)
{ k=0;
for(j=1;j<=i;j++)
{
if((i%j)==0)
k++;
}
if(k==2)
cout<<i<<endl;
}
getch();
}
Antwoord 20
Ik gebruik deze altijd (het is gemakkelijk en snel):
#include <iostream>
using namespace std;
int i,j;
bool b[101];
int main( )
{
for(i=2;i<101;i++){
b[i]=true;
}
for(i=1;i<101;i++){
if(b[i]){
cout<<i<<" ";
for(j=i*2;j<101;j+=i) b[j]=false;
}
}
}
Hier is de uitvoer van deze code:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Antwoord 21
Hoewel dit relatief meer priemgetalgenerator van productiekwaliteit is, is het nog steeds geldig om te gebruiken voor het vinden van priemgetallen van 1 tot 100. De code gebruikt Miller-Rabin Primality Testom priemgetallen te berekenen. Omdat het een probabilistische methode is, neemt de nauwkeurigheid toe met de waarde van k. Hoewel de nadruk ligt op leesbaarheid van code in plaats van snelheid, op AWS r5.2xlargehet duurde bijvoorbeeld 3.791s voor priemgetal tot 1.000.000.
// C++ program to print all primes smaller than or equal to
// n using Miller-Rabin Primality Test
// Reference: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
// It is not particularly to optimized
// since focus is readability
// Compile: g++ -std=c++17 -o prime prime.c++ -ltbb
#include <execution>
#include <iostream>
#include <math.h>
using namespace std;
int power(unsigned long int x, unsigned long y, unsigned long p){
int res = 1;
x = x % p;
while (y > 0) {
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
bool millerTest(unsigned long d, unsigned long n) {
unsigned long a = 2 + rand () % (n - 4);
unsigned long x = power(a, d, n);
if (x == 1 || x == n - 1)
return true;
while (d != n - 1){
x = (x * x) % n;
d *= 2;
if (x == 1) return false;
if (x == n - 1) return true;
}
return false;
}
bool isPrime(unsigned long n, int k) {
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
unsigned long int d = n - 1;
while (d % 2 == 0)
d /= 2;
for(int i = 0; i < k; i++){
if (!millerTest(d, n))
return false;
}
return true;
}
int main()
{
int n = 1000000;
int k = 200;
vector<unsigned long> primeN(n);
iota(primeN.begin(), primeN.end(), 1);
vector<bool> isPrimeV(n);
transform(execution::par,
primeN.begin(), primeN.end(),
isPrimeV.begin(),
[k](unsigned long x) -> bool {
return isPrime(x, k);
});
int count = accumulate(isPrimeV.begin(), isPrimeV.end(), 0, [](int d, bool v){
if (v == true) return d += 1; else return d;
});
cout << count << endl;
return 0;
}
Antwoord 22
Probeer dit gewoon.
Het is gemakkelijk zonder extra ingebouwde functies.
#include <iostream>
int prime(int n,int r){
for(int i=2;n<=r;i++){
if(i==2 || i==3 || i==5 || i==7){
std::cout<<i<<" ";
n++;
} else if(i%2==0 || i%3==0 || i%5==0 || i%7==0)
continue;
else {
std::cout<<i<<" ";
n++;
}
}
}
main(){
prime(1,25);
}
Testen door 2,3,5,7is goed genoeg voor maximaal 120 , dus 100is OK.
Er zijn 25priemgetallen onder 100, een 30onder 121 = 11*11.