Prvočísla - JAVA (cyklus while,for) – Java – Fórum – Programujte.com

Dobrý den.

Dostal jsem ve škole úkol a nevím co s tím.

Mám vytvořit program (v programovacím jazyce JAVA), na začátku kterého zadáme číslo a program zjistí zda-li dané číslo je a nebo není prvočíslo.

Daný program by měl být vytvořen za pomocí cyklu while a nebo for.

Předem děkuji za odpověď. 

tak zacnes tim, jak vlastne poznas, ze je cislo prvocislo?

zaujimave to tlacidlo "odpovedet" v tomto pripade straca zmysel kedze nebola polozena otazka ... v podstate je rovnako zbytocny aj thread ...

sice se z toho asi nic nenaucis, ale tady je naivni implementace:

package primenumber;

/**
 *
 * @author Jiri Prajzner
 */
public class PrimeNumber {

  /**
   * @param args the command line arguments
   */
  public static void main(String[] args) {
    if ((Integer.parseInt(args[0].trim()) % 2) != 0) {
      System.out.println(args[0] +" is a prime number.");
    } else {
      System.out.println("args[0] +" is not a prime number");
    }
  }
}

bylo by vhodne kdyby jsi jako bonus napred zjistil v jakem oboru je tohle reseni platne a podle toho validoval argumenty. pokud se ti chce, implementuj lepsi algoritmus pro nalezeni prvocisla, na interneu je toho spousta.

#4 Jiri Prajzner
toto ti akorát rozliší, zda je číslo liché :)

#5 crazy
spravne :)

takže si myslíte, že když je číslo liché, tak se jedná o prvočíslo?

#7 crazy
tim "naivni" bude asi mysleno "uplne blba"

Poslední příklad v tomto článku je na prvočísla, řešeno pomocí cyklu for - stačí těch pár příkazů přepsat :).

for (int j = 2; j <= (int) Math.sqrt(n); j++) {
            if (n % j == 0) {
                isPrime = false;
                break;
            } else {
                isPrime = true;
            }
        }
        if (isPrime) {
            System.out.println(n + " je prvočíslo");
        } else {
            System.out.println(n + " neni prvočíslo");

Pozri si nieco o malej Fermatovej vete. Plati ze ak a jelubovolne cele (nezaporne) cislo a p je prvocislo => a^(p-1) == 1 (mod p). Cize zapis pre javistu Math.pow(a, (p-1))%p == 1. Metoda podobna tejto sa v dnesnej dobe pouziva v RSA. Pozor na ten znak implikacie, to neplati opacne, ze ak ti z najkych takto zadanych cisel vyde 1 tak p je prvocislo. Prikl. a=1; p=4; 1^3 =1; 1%4=1 ale vieme ze p urcite nieje prvocislo. Cize je vyhodne to vypocitat pre viacero roznych a. A aby to fungovalo ako tak effektivne, je dobre za kazdym umocnennim urobit modulo (toto cele ma nieco docinenia z cyklickymy konecnymi grupami). Takto by som to riesil ja:

public int powMod(int a, int p) {
	int out = 1;
	int exp = p-1;
	for(int k=0; k<32;k ++) {
		if (exp %2 ==1 ) {
			out = (out * a)%p;
		}
		exp= exp>>1; // exp/2
		a = (a*a)%p; // umocnenie priamo z modulovanim
				// inak by si dostal velke cisla
	}
	return out;
}

Inak som si vsimol ze ak zajdes do BigInteger classu taketo veci tam priamo su. A je tam aj metoda isProbablyPrime, ktora bude zrejem fungovat na tomto principe. Dokonca je tam aj metoda powMod() co som do pisania tejto metody nevedel :D.

#11 sleepy
pre ludi ktory by sa zase chceli hadat o konvergencii a divergencii, napisal som si to v pythone , funguje to. Diverkovat to na konecnom pocte nasobeni nemoze ak, jedno z tych cisel samo nieje nekonecno resp. lim k->inf. To ze robime z konecnymi poctami bytov neznamena ze nieco nekonverguje. A za tretie je tam modulo ktore to za kazdym hodi na cislo mensie ako p!

a etse jedna vec ak a > p > 2^16 je dobre spravit: a = ((a%p)*(a%p))%p;

Neviem ci si to mozem dovolit, ale postnem tu link peknych videi o prvocislach v jednom kanale: http://www.youtube.com/watch?v=iFuR97YcSLM. Mozno to niekoho troska bude zauimat.