#include <iostream>
#include <ctime>
#include<fstream>
#include <utility>
#include <algorithm>
using namespace std;
// ----------------------chooser---------------------
int nextPrime(int p, bool s[])
{
int i = p;
do
{
i++;
}
while (!s[i]);
return i;
}
// ------------------- end chooser --------------------
// -----------------------generator----------------------------
void generator(int p, int e, int n, bool s[])
{
int l = (e - p + 1);
int start = e + 1;
int end = (p) * l + nextPrime(p,s) - 1;
if (end >= n || end < 0)
{
end = n;
}
for (int i = start; i <= end; i++)
{
s[i] = s[i - l];
}
}
// -------------------end generator------------------------
unsigned int e, p, n;
// ---------------------cleaning---------------------------
void cleaning(int p, int e, bool s[])
{
for (int i = e; i >= p; i--)
{
if (s[i])
{
s[i * p] = false;
}
}
}
// ----------------end cleaning------------------
int main()
{
bool *s;
cout << "Enter the maximum number: ";
cin >> n;
clock_t start = clock();
s= new bool[(max(n + 1u, 6u))];
e = 2;
p = 2;
s[2] = true;
s[3] = true;
s[5] = true;
do
{
generator(p, e, n, s);
cleaning(p, e, s);
e = p * (e - p + 1) + nextPrime(p, s) - 1;
p = nextPrime(p, s);
}
while ((p * e <= n && p * e > 0));
generator(p, e, n, s);
do
{
cleaning(p, n/p, s);
p = nextPrime(p, s);
}
while (p * p <= n);
float timeA =(float)(clock() - start)/1000;
cout << ( "Action time = " );
cout << timeA << " s";
//----------------------------- RECODR TO FILE --------------------------
ofstream record ("prime.txt");
int k=0;
for (int i=0; i<= n; i++)
{
if(s[i])
{
k+=1;
record << i <<" ";
if (k%25==0)
{
record << "
";
}
}
}
record.close();
delete [] s;
return 0;
}
Ostatnio zmieniony 15 gru 2017, o 20:02 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód:Poprawa wiadomości.
Mógłbyś skomentować jakoś metodę wyznaczania tych liczb pierwszych? Przez ten kod trudno się przebić. Albo może ponazywaj zmienne tak, by było wiadomo, co mają robić?
W opracowaniu jest to dokładnie opisane, tutaj wychodzi jakoś nieczytelnie.
s - tablica logiczna
n - max
p - liczba pierwsza
e - koniec cyklu
end - koniec nowego cyklu
start - początek cyklu
l - długość cyklu
No nie dogadamy się:D Weź, wytłumacz po prostu jaka jest metoda generowania liczb pierwszych, albo wstaw ten element kogu, który za to odpowiada - bez liczenia czasu itp. itd.
Z samego kodu trudno wyłapać dlaczego tak - to jest przejście z innej metody dla ciągów liczb z przyrostami cyklicznymi do tablic booleanowych. Wejdź na Teorię Liczb tam zacząłem temat Generowania. Spróbuj wykonać zabawę w tabelki to od razu zrozumiesz na czym polega zabawa.
No ok - tak zrobię, ale pamiętaj, ze jeśli Twój algorytm jest rzeczywiście szybki i nowy, to i tak żaden informatyk się nim, nie zainteresuje, dopóki nie wytłumaczysz dokładnie co się dzieje (taka rada na przyszłość).
Byłbyś w stanie rozpisać nam schemat blokowy/inną metodą algorytm, którego używasz dokładnie? Wytłumaczenie sprawi, że nabierze to jakiejś wartości... W tym momencie to przypominasz mi tylko pana L. W. G. XD
Wystarczy wczytać się w opracowanie - opis jest raczej wystarczający z dokładnym rozpisaniem w pseudokodzie.-- 19 gru 2017, o 00:38 --Kod ma wartość taką, że działa bezbłędnie i najszybciej na świecie. Już nie musi nabierać wartości.
Kod ma wartość taką, że działa bezbłędnie i najszybciej na świecie. Już nie musi nabierać wartości.
No tak, ale dowód jest konstruktem społecznym, jeżeli społeczność nie uzna Twojego algorytmu za poprawny, to Twoje rozwiązanie zostanie szybko zapomniane.
public class MRSieveCPlus {
public static boolean[] s;
// ----------------------chooser---------------------
public static int nextPrime(int p, boolean s[]) {
int i = p;
do {
i++;
} while (!s);
return i;
}
// ------------------- end chooser --------------------
// -----------------------generator----------------------------
public static void generator(int p, int e, int n, boolean s[]) {
int l = (e - p + 1);
int start = e + 1;
int end = (p) * l + nextPrime(p, s) - 1;
if (end >= n || end < 0) {
end = n;
}
for (int i = start; i <= end; i++) {
s = s;
}
}
// -------------------end generator------------------------
int e, p, n;
// ---------------------cleaning---------------------------
public static void cleaning(int p, int e, boolean s[]) {
for (int i = e; i >= p; i--) {
if (s) {
s[i * p] = false;
}
}
}
// ----------------end cleaning------------------
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("Enter the maximum number ");
int n = in.nextInt();
in.close();
int startTime = (int) System.currentTimeMillis();
if (n >= 5) {
s = new boolean[n + 1];
} else {
s = new boolean[6];
}
int e = 2;
int p = 2;
s[2] = true;
s[3] = true;
s[5] = true;
do {
generator(p, e, n, s);
cleaning(p, e, s);
e = p * (e - p + 1) + nextPrime(p, s) - 1;
p = nextPrime(p, s);
} while ((p * e <= n && p * e > 0));
generator(p, e, n, s);
do {
cleaning(p, n / p, s);
p = nextPrime(p, s);
} while (p * p <= n);
int estimatedTime;
estimatedTime = (int) (System.currentTimeMillis() - startTime);
System.out.println("Action Time = " + estimatedTime + " Quantity " + (n));
// ----------------------------- RECODR TO FILE
// --------------------------
PrintWriter record = null;
try {
record = new PrintWriter("Prime.txt");
} catch (FileNotFoundException w) {
w.printStackTrace();
}
int k = 0;
for (int i = 0; i <= n; i++) {
if (s) {
if (s) {
k = k + 1;
record.print(i + " ");
}
if (k % 25 == 0) {
record.println();
}
}
}
record.close();
}
}
-- 9 sty 2018, o 11:03 --Proszę administratora o przeniesienie kodu Java na początek tematu- jeżeli można chciałbym by oba kody były z nagłówkami w hidenie.
Brombal pisze:Wystarczy wczytać się w opracowanie - opis jest raczej wystarczający z dokładnym rozpisaniem w pseudokodzie.
-- 19 gru 2017, o 00:38 --
Kod ma wartość taką, że działa bezbłędnie i najszybciej na świecie. Już nie musi nabierać wartości.
Z tym "najszybciej na świecie" to bym nie przesadzał, polecam . O złożoności pamięciowej chyba zupełnie zapomniano, szkoda - przez to program jest bezużyteczny.
Rzuciłeś może okiem na polecany przez Ciebie program?
Faktycznie jest najszybszy i możesz nawet policzyć ilość liczb pierwszych a nawet bliźniaczych. Zmierzy również czas pracy. Ale jeżeli będziesz chciał zobaczyć albo zapisać wynik swojej pracy... To zastosuj lepiej klasycznego Eratostenesa będziesz krócej czekał na wynik.
To taka wyścigówka ale zapomnieli o miejscu dla kierowcy a nawet karoserii - taka metoda zmniejszania masy pojazdu.
Pozdrawiam
