Простое число в java 8

Question

Простое число в java 8

Я пытался написать простую программу для простых чисел на Java 8. Ниже приведена программа. Я также хотел сократить код в isPrime(). Есть ли что-то, что фильтрует элементы от 2 до n/2, а затем применяет фильтр для n%i == 0, который сделал бы isPrime нерелевантным?

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;

    }

}

777 4

java java-8 primes

4 ответов:

Comments

Ничего не найдено.

Shashwat Kumar · Accepted Answer · 2017-06-05 14:34:32

IntStream можно использовать для генерации целочисленного потока
public static boolean isPrime(int number) {
    return !IntStream.rangeClosed(2, number/2).anyMatch(i -> number%i == 0); 
}
Или
public static boolean isPrime(int number) {
    return IntStream.rangeClosed(2, number/2).noneMatch(i -> number%i == 0);
}

rossum · Accepted Answer · 2017-06-05 17:41:56

Ваш isPrime() неэффективен. Во-первых, вам не нужно делить на какие-либо четные числа больше 2, так как начальное деление на 2 будет ловить все четные не простые числа. Во-вторых, вы завершаете цикл на number / 2 вместо более эффективного sqrt(number).

Вы можете переписать свой метод примерно так:
public static boolean isPrime(int number) {

    // Even numbers
    if (number % 2 == 0) {
        return number == 2;
    }

    // Odd numbers
    int limit = (int)(0.1 + Math.sqrt(number));
    for (int i = 3; i <= limit; i += 2) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}
Сито Эратосфена было бы еще более эффективным, но это могло бы быть излишним для относительно небольшой проблемы.

Eugene · Accepted Answer · 2017-06-06 12:44:59

Как предлагает @rossum, вы можете использовать знаменитое сито Эратосфена для этого, и оно вычислит простые числа довольно быстро.
 private static BitSet primes(int limit) {
    BitSet bitSet = new BitSet(limit);
    bitSet.set(0, false);
    bitSet.set(1, false);
    bitSet.set(2, limit, true);

    for (int i = 2; i * i < limit; ++i) {

        if (bitSet.get(i)) {
            int j = i;
            int x = 2;
            while (j < limit) {
                j = i * x;
                bitSet.set(j, false);
                ++x;
            }
        }

    }

    return bitSet;
}

Deep · Accepted Answer · 2018-06-19 20:43:56

Вы также можете достичь желаемого, используя предикат.

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()));
     }

}