Bem, se vc quer um programa que calcule os números primos, assim na lata, prontinho, então pode ser da maneira como nós achamos melhor né?!
qualquer coisa, se quizer ver o código original (não fui eu que fiz):
http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/Pratt/Prime.java
Agora se vira para entender e explicar para seu professor, vc queria um programa que mostrasse os primos, ta ai ele… se vc quer uma coisa mais simples, faz ai e posta as duvidas que vc tem para fazer
O segundo problema, hmmm vou procurar uma solução no estilo da dos números primos, se achar eu posto ai.
import java.util.ArrayList;
import java.util.List;
class Prime {
private int p;
private boolean isPrime = false;
private List<Integer> rList = new ArrayList<Integer>();
private List<Integer> qList = new ArrayList<Integer>();
private int rZeuge;
public Prime(int number) {
p = number;
LucasFindR();
PFZ();
LucasTestFast();
return;
}
public static void main(String[] args) {
List<Integer> primos = new ArrayList<Integer>();
for (int i = 2; i <= 200; i++) {
if (new Prime(i).isPrime()) {
primos.add(i);
}
}
for (Integer primo : primos) {
System.out.println(primo);
}
}
public boolean isPrime() {
return isPrime;
}
public int getRZeuge() {
return rZeuge;
}
public List getQList() {
return qList;
}
public List getRList() {
return rList;
}
public List LucasComplete() {
List<List<String>> result = new ArrayList<List<String>>();
int i, j, q, r;
q = 0;
for (i = 0; i < rList.size(); i++) {
result.add(new ArrayList<String>());
r = rList.get(i);
for (j = 0; j < qList.size(); j++) {
q = qList.get(j);
if (Formel(r, (p - 1) / q, p) == 1) {
result.get(result.size() - 1).add("-");
} else {
result.get(result.size() - 1).add("+");
}
}
}
return result;
}
public List LucasFindR() {
int r;
for (r = 2; r < p; r++) {
if (Bedingung1(r)) {
rList.add(r);
}
}
return rList;
}
public List PFZ() {
qList = PFZ(p - 1);
return qList;
}
private void LucasTestFast() {
int r;
for (r = 2; r < p; r++) {
if (Bedingung1(r)) {
if (Bedingung2(r)) {
rZeuge = r;
isPrime = true;
return;
}
} else {
return;
}
}
return;
}
private boolean Bedingung1(int r) {
if (Formel(r, p - 1, p) == 1)
return true;
else
return false;
}
private boolean Bedingung2(int r) {
int i, q = 0;
for (i = 0; i < qList.size(); i++) {
if (q != qList.get(i)) {
q = qList.get(i);
if (Formel(r, (p - 1) / q, p) == 1)
return false;
}
}
return true;
}
private List<Integer> PFZ(int x) {
int q;
List<Integer> PFTemp = new ArrayList<Integer>(10);
for (q = 2; q < x; q++) {// test all possible factors
if (x % q == 0) {// q is prime factor of x
PFTemp.add(q);
// eliminate this factor
x /= q;
q--;
}
}
PFTemp.add(x);
return PFTemp;
}
int Formel(int a, int b, int c) {
int k, bitmask, d, i;
k = 30;
bitmask = 0x40000000;
d = 1;
for (i = k; i >= 0; i--) {
d = (d * d) % c;
if ((b & bitmask) > 0) {
d = (d * a) % c;
}
bitmask /= 2;
}
return (d);
}
}
