Prime number in java 8

user_3310115 0
Viewed 33185

I was trying to write a simple prime number program in Java 8. Below is the program. I wanted to reduce the code in isPrime() as well. Is there something that filters the elements from 2 to n/2, and then apply filter for n%i == 0 which would make isPrime irrelevant?

import static java.util.stream.Collectors.toList;

import java.util.Arrays;
import java.util.List;
import java.util.function.Predicate;

public class Stream1 {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 20);
        // Prime number 
        System.out.println(numbers.stream()
                             .filter(Stream1::isPrime)
                             .collect(toList()));
    }

    public static boolean isPrime(int number) {
        for (int i = 2; i <= number / 2; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}
java-8 primes java
9 Answers

You can use algorithm Sieve of Eratosthenes like this

public static IntStream primes(int max) {
    IntStream primes = IntStream.range(2, max);
    IntFunction<IntPredicate> sieve = n -> i -> i == n || i % n != 0;
    primes = primes.filter(sieve.apply(2));
    for (int i = 3; i * i <= max; i += 2)
        primes = primes.filter(sieve.apply(i));
    return primes;
}

and

System.out.println(primes(100).count());    // -> 25
System.out.println(primes(1000).count());   // -> 168
System.out.println(primes(10000).count());  // -> 1229
Admin1

You can use stream as this test below:

@Test
public void generatePrimeNumberListByStream(){
    List<Integer> primeNumbers =
            IntStream
                    .range(2,30)
                    .filter(number -> IntStream.range(2,number)
                            .noneMatch(divider -> number % divider == 0))
                    .boxed()
                    .collect(Collectors.toList());
    assertThat(primeNumbers, contains(2,3,5,7,11,13, 17,19, 23, 29));
}
user_78269810 
public static boolean isPrime(int i) {
    return i % 2 != 0 && IntStream.iterate(
            3, n -> n <= (int)(Math.sqrt(i)), n -> n + 2)
            .noneMatch(k->i%k==0);
}

iterate takes 3 parameters, similar to a for loop, base is the start, the second is the stop condition, third is the increment rule. 1 and 2 are prime already so we start at 3 and we stop before reaching the square root of the number. The idea is that suppose n is a positive integer n=pq, where p and q are prime numbers. Assume p greater than square root of n and greater than square root of n. Multiplying these inequalities we have p*q > sqrt n * sqrt n, which implies pq > n. This is a contradiction to our hypothesis n=pq. Hence we can conclude that either p less or equal sqrt n or q less than equal sqrt n.

n -> n <= (int)(Math.sqrt(i))

finally we do not need to check even numbers as long as it is not divisible by 2 so we only try every second number.

(n -> n+2)

user_74147190 
public static void main(String[] args) {
    List<Integer> list = IntStream.range(0, 100).filter(i -> isPrime(i)).boxed().collect(Collectors.toList());
    System.out.println(list);

}

static boolean isPrime(int number) {
    return number > 1 && IntStream.rangeClosed(2, number/2).noneMatch(i -> number % i == 0);
}
user_58457620

You can achieve the desired using predicate as well.

import java.util.Arrays;
import java.util.List;
import java.util.function.IntPredicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class PrimeUsingStream {

     public static boolean isPrime(int i) {
            IntPredicate isDivisible = index -> i % index == 0;
            return i > 1 && IntStream.range(2, i).noneMatch(isDivisible);
     }

     public static void main(String[] args) 
     {

        //System.out.println(printPrime(200));

         List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 20,23);
            // Prime number 
        System.out.println(numbers.stream()
                                 .filter(PrimeUsingStream::isPrime)
                                 .collect(Collectors.toList()));
     }

}
user_64363980

Java8+ solution

public static boolean isPrime(long number) {
    return number>1 && LongStream.rangeClosed(2, number / 2).noneMatch(i -> number % i == 0);
}

need to exclude 1!!

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers.

https://en.wikipedia.org/wiki/Prime_number

user_14985370
Related