Reputation: 43
One of the tasks of my homework assignment was to find all prime numbers within a certain length in an array. However, I am having trouble trying to find prime numbers without using modulus or multiplication or division. Any help would be much obliged. The part I'm having difficulty is marked "Testing if it's divisible by other numbers beside 1 and itself."
Here is my code:
class A {
public static void sieve(int [] array) {
//List of primes
int [] primes;
primes = new int[1000000];
//Setting the Array
for(int i = 1; i < array.length; i++) {
array[i] = i;
}
//Finding Primes
System.out.println("Your primes are: ");
for(int j = 0; j < array.length; j++) {
boolean prime = true;
int num = array[j];
//Testing if it's divisible by other numbers beside 1 and itself.
for(int n = 2; n < j; n++) {
num -= n;
if(num == 1) {
prime = false;
}
}
Upvotes: 2
Views: 3311
Reputation: 376
If you need the list of prime number without using modulus, division, or multiplication you have to use Sieve of Eratosthenes
.
const int SIZE=100010;
int status[SIZE]={1};
int sieve(){
for(int i=0;i<=SIZE;i++)
status[i]=1;
for(int i=2;i<=SIZE;i++){
if(status[i]==1){
for(int j=2*i;j<=SIZE;j+=i){
status[j]=0;
}
}
}
}
int main(){
sieve();
//check from 2 to 100 which one is prime and which one is not prime
for(int i=2;i<100;i++){
if(status[i]==0)
printf("%d NOT PRIME\n",i);
else if(status[i]==1)
printf("%d PRIME\n",i);
}
}
Upvotes: 1