Liczby pierwsze - java

0

Mam za zadanie napisanie programu, który dla podanych liczb naturalnych wypisze je w kolejnych liniach z informacją czy jest to liczba pierwsza, czy nie.

Coś napisałem, proszę o sprawdzenie kodu pod względem wydajności, funkcjonalności, być może można coś dodać, przerobić

public class pierwsze 
        {        
                public static boolean prime(int n) 
                { 
                        if (n>2) 
                        { 
                        double sq = Math.sqrt(n); 
                        if(n%2==0) 
                        return false; 
                                else 
                                { 
                                for(int i=3; i<=sq; i+=2) 
                                        { 
                                                if(n%i==0) 
                                                { 
                                                return false; 
                                                } 
                                        } 
                                        return true; 
                                                } 
                                                } 
                else if (n==2) return true; 
                return false; 
                                } 
        
        
        public static void main(String args[]) 
        { 
        int n=0; 
        for(int i=0; i<args.length; i++) 
        { 
                try 
                { 
                        n=Integer.parseInt(args[i]); 
                        if (prime(n)) System.out.println(n + " jest liczba pierwsza"); 
                        else System.out.println(n + " nie jest liczba pierwsza"); 
                                } 
                                catch (NumberFormatException ex) 
                                { 
                                System.out.println(args[i] + " nie jest liczba calkowita"); 
                                }                      
                        } 
        } 
} 




 
0

Wygląda nieźle. Widzę dwie usterki:

  • co z liczbami ujemnymi
  • komunikat typu "222222222222222222222222222222222 nie jest liczba całkowitą" będzie wyglądał dziwnie.
0

Dla liczb ujemnych będzie wyświetlał się komunikat, że taka liczba nie jest liczbą pierwszą, natomiast dla ogromnych liczb .... coś tutaj należy zmienić, chyba, że dla takich liczb zakres zostaje przekroczony.

0
  • popraw formatowanie kodu (klamry, wcięcia)
  • nazwa klasy z reguły rozpoczyna się wielką literą
  • nazwa metody, zgodnie z konwencjami, powinna być "isPrime(int n)" -> bo zwraca boolean
  • komunikat dla wyjątku zmień na "nie jest poprawną liczbą typu integer"
0

Prócz tego coś jeszcze należałoby zmienić?
czy sposób znajdywania liczb pierwszych jest poprawny?

0
if(n<2) return false;
if(n%2==0) return n==2;
if(n%3==0) return n==3;
//if(n<25) return true;
for(i=5; i<=sq ; n=n+6){  // omijamy także krotności 3
    if(n%i==0) return false;
    if(n%(i+2)==0) return false;}
0

LooooooooooooooooooooooooooooooooooooooooooooooooooooooooooL
http://pl.wikipedia.org/wiki/Sito_Eratostenesa i masz tam nawet implementację w Javie.

0

ale sitem Eratostenesa raczej nie za bardzo będę w stanie wpisać odpowiednie liczby i wiedzieć, czy jest pierwsza, czy nie?

0

Jak to nie? Dostajesz zbiór liczb, wybierasz z nich największą i do jej wartości liczysz sito. Na koniec już tylko sprawdzasz czy jakaś liczba ze zbioru wejściowego została odsiana (jako pierwsza) czy skreślona.

0

Wybór, sito czy funkcja isPrime() powinien zależeć od ilości liczb, których "pierwszość" chcemy zbadać. Jeżeli n=15 485 857 (liczba jest pierwsza, i jest typu int), to czas wykonania funkcji isPrime(n) wynosi 0.2 ms., a czas stworzenia sita wynosi około 500 ms. Celowo wybrałem liczbę pierwszą, by sprawdzanie trwało długo. Ponieważ program uruchamiamy tak java pierwsze liczba1 liczba2 ..., to jest mało prawdopodobne by ilość liczb była duża. Uważam zatem użycia sita za nieuzasadnione.

0

a tak w ogóle czy ten kod, który podałem wyżej jest poprawny, bo Xitami napisał, że coś tam mogę dodać, ale czy tak nie może zostać, chodzi mi o sa.m kod , który dla podanych konkretnych liczb wypisuje czy jest to liczba pierwsza.

Sito Eratostenesa mogę użyć, mam nawet gotowy kod na wikipedii, ale mógłby ktoś podrzucić jakiś pomysł, w jaki sposób zmienić ten kod bym mógł wypisywać liczby i sprawdzać, jaka to liczba?
czy może wystarczy lekko podrasować kod który mam i będzie dobrze?

0

Sito, to zupełnie innych kod. Zresztą bardzo prosty (w wersji jednowątkowej).

0

więc co proponujecie czego użyć?

0

Takiego sita jak np. to poniżej.
Jak widać metoda przeliczSito jest banalnie prosta i bardzo szybka. Zawiera tylko (number - 2) dzieleń całkowitych, reszta to same dodawania. Czas policzenia największej liczby pierwszej jest jednocześnie czasem policzenia wszystkich mniejszych od niej, więc po policzeniu największej dane są wypluwane taśmowo (liczy się tylko czas dostępu do tablicy BitSet). Ponieważ informacja o każdej liczbie zajmuje tylko 1 bit, więc jest również najbardziej optymalna pamięciowo.
Można też uzyskać informację o liczbie znalezionych liczb pierwszych, ponieważ jest to liczba zgaszonych bitów w tablicy "podzielna". BitSet udostępnia liczbę bitów ustawionych oraz największy ustawiony, więc łatwo policzyć zgaszone.

package com.olamagato.util;
import java.util.BitSet;

/**
 * Pozwala szybko wyszukać 32-bitowe liczby pierwsze.
 * Wersja lokalna, jednowątkowa, niesynchronizowana.
 * Optymalna jest globalna, wielowątkowa (ForkJoinTask), synchronizowana
 * Do policzenia Integer.MAX_VALUE potrzeba
 * 256 MB + 32 bajty pamięci JVM oraz dwie kawy.
 * @author Olamagato
 */
public class FreePrimes
{
	public FreePrimes(final int maxNumber)
	{
		this.podzielna = new BitSet(maxNumber);
		init();
	}

	public FreePrimes()
	{
		this.podzielna = new BitSet();
		init();
	}

	private void init()
	{
		podzielna.set(0, 1);
		największaPoliczona = 3;
	}

	/**
	 * Informuje czy liczba jest pierwsza.
	 * W tym celu przelicza lub dolicza sito Erastotenesa
	 * od największaPoliczona do number.
	 * @param number liczba do sprawdzenia
	 * @return true jeżeli number jest liczbą pierwszą
	 */
	public boolean isPrime(final int number)
	{
		if(number > największaPoliczona)
			przeliczSito(number);
		return !podzielna.get(number);
	}

	/**
	 * Zwraca największą liczbę pierwszą nie większą niż number lub -1.
	 * Jeżeli number jest liczbą pierwszą to jest ona zwracana jako wynik.
	 * @param number górny zakres sprawdzanego zbioru liczb pierwszych
	 * @return największa liczba pierwsza z zakresu [2, number] lub -1
	 */
	public int getLargestPrime(final int number)
	{	//nowa metoda BitSet.previousClearBit() dodana w Javie 1.7
		return isPrime(number) ? number : podzielna.previousClearBit(number);
	}

	/**
	 * Uzupełnia sito przez wykreślenie wielokrotności licz od
	 * number do największaPoliczona.
	 * Wersja jednowątkowa.
	 * @param number liczba, do której przeliczane jest sito
	 */
	private void przeliczSito(final int number)
	{	//dokłada brakujące skreślenia od największaPoliczona do number
		for(int skreśl = 2; skreśl <= number ; ++skreśl)
		{	//skreśla tylko wielokrotności liczby do skreślania zaczynając
			//od największaPoliczona (omija wcześniejsze skreślenia)
			final int liczOd = największaPoliczona >= skreśl ?
				największaPoliczona - największaPoliczona % skreśl : skreśl;
			//skreśla kolejne wielokrotności
			for(int n = liczOd + skreśl; n <= number; n += skreśl)
				podzielna.set(n);
		}
		największaPoliczona = number;
	}

	/**
	 * Bit zawierający false oznacza liczbę pierwszą, true oznacza
	 * wykreślony mnożnik. Liczby 0 i 1 muszą być ustawione jako true
	 * z definicji.
	 */
	private final BitSet podzielna;
	private int największaPoliczona; //największa dotychczas policzona

	//testy

	public static void main(String[] args)
	{
		final int PR = 15485857; //spora liczba pierwsza
		int[] testy = { 18, 40, 97, 100, PR, 16_000_000, 18_000_000 };
		FreePrimes pierwsze = new FreePrimes(32_000_00);
		for(int i: testy)
			test(pierwsze, i);
	}

	@SuppressWarnings("UseOfSystemOutOrSystemErr")
	private static void test(FreePrimes primes, int liczba)
	{
		Boolean isPrime = Boolean.valueOf(primes.isPrime(liczba));
		System.out.printf("Czy %d jest pierwsza? %s",
			liczba, isPrime ? "Tak" : "Nie");
		if(!isPrime)
			System.out.printf(", największa liczba pierwsza <= %d to %d",
				liczba, primes.getLargestPrime(liczba));
		System.out.println();
	}
}

Output:
Czy 18 jest pierwsza? Nie, największa liczba pierwsza <= 18 to 17
Czy 40 jest pierwsza? Nie, największa liczba pierwsza <= 40 to 37
Czy 97 jest pierwsza? Tak
Czy 100 jest pierwsza? Nie, największa liczba pierwsza <= 100 to 97
Czy 15485857 jest pierwsza? Tak
Czy 16000000 jest pierwsza? Nie, największa liczba pierwsza <= 16000000 to 15999989
Czy 18000000 jest pierwsza? Nie, największa liczba pierwsza <= 18000000 to 17999987
0

@Olamagato:

  1. "Sito Eratostenesa jest najszybszą znaną metodą..."
    nie jest!
    bo np. Aitken
    nawet niby prostego Eratostenesa można zrobić lepij lub gorzej (wielkie tablice, jak zachowa się cache?)

  2. " informacja o każdej liczbie zajmuje tylko 1 bit, więc jest również najbardziej optymalna pamięciowo"
    czyli trwonisz pamięć na np. parzyste, wsród kolejnych 30 liczb góra 8 może być pierwsza, wsród 210 tylko....

Po pierwsze primo - ile liczb i jak wielkich
a później można się spierać o wyższość którychś tam świąt
bo czasem

s=0;
for(i=1; i<=n; i++)
    if( n%i==0 )
        s++;
return s==2;

jest wystarczające

1 użytkowników online, w tym zalogowanych: 0, gości: 1