solorzke
solorzke

Reputation: 43

Finding Prime Numbers without using modulus, division, or multiplication

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

Answers (1)

Sakib Rahman
Sakib Rahman

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

Related Questions