Подсчет не простых чисел

Question

Я хотел бы создать метод, который будет возвращать число не простых чисел из массива int.

Метод, который я использую для пометки простых чисел в массиве, выглядит следующим образом (эта часть не нуждается в каких-либо изменениях):

public static int markNonePrimeNumbers(int[] array) {
        createInitialArray(100);
        for (int j = 2; j < array.length; j++) {
            for (int i = j * 2; i < array.length; i += j) {
                array[i] = 0;
            }
        }

Я хочу изменить его, чтобы он мог вернуть числа массива [i] = 0 и считать его.

Я зашел так далеко, добавив HashMap:

public static int[] markNonePrimeNumbers(int[] array) {
    createInitialArray(100);
    for (int j = 2; j < array.length; j++) {
        for (int i = j * 2; i < array.length; i += j) {
            array[i] = 0;
        }
    }
    Map<Integer, Integer> map = new HashMap<>();
    for (int key : array) {
        if (map.containsKey(key)) {
            int occurrence = map.get(key);
            occurrence++;
            map.put(key, occurrence);
        } else {
            map.put(key, 0);
        }
    }
    for (Integer key : map.keySet()) {
        int occurrence = map.get(key);
        System.out.println(occurrence);
    }

В общем, я близко, но я не знаю, как удалить все индексы с карты выше 1. Уже вычислено значение 0 для первого индекса.

Answer 1

Ваш метод вычисления простых чисел был неверным, и, следовательно, ваш счет не был правильным. Вы подходите, чтобы посчитать количество не простых чисел почти на точке.

Я немного изменил код для корректной работы здесь

public static void main(String[] args){

        int[] array = new int[]{1,2,3,4,57,10,7,11,13,17,16};
        for (int i = 0; i < array.length; i++) {
            int temp = 0;
            for(int j=2;j<=array[i]/2;j++)
            {
                temp=array[i]%j;
                if(temp==0)
                {
                    array[i] = 0;
                    break;
                }
            }
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int key : array) {
            if (map.containsKey(key)) {
                int occurrence = map.get(key);
                occurrence++;
                map.put(key, occurrence);
            } else {
                map.put(key, 1);
            }
        }
        if(map.containsKey(0)){
            System.out.println(map.get(0));
        } else {
            System.out.println("could not find");
        }
    }

Answer 2

Один из лучших способов сделать это - сохранить текущий список простых чисел, а затем проверить список. Первая часть - это код драйвера, поэтому он не нуждается в объяснении.

        int[] array = new int[] { 1,19, 2, 3, 4, 57, 10, 7, 11,
                13, 17, 16 };
        List<Integer> nonPrimes = new ArrayList<>();
        for (int c : array) {
            if (!isPrime(c)) {
                nonPrimes.add(c);
            }
        }
        System.out.println(nonPrimes);

Вот начало метода простого поиска. Ключевые моменты:

1. Он использует LinkedHashSet для хранения простых чисел.
   a. Поддерживает порядок.
   б. Позволяет быстро найти определенное значение c

2. Находит все простые числа до заданного значения и сохраняет их. Это делается только в том случае, если переданное значение больше, чем последнее записанное простое число.

3. Последующие простые числа-кандидаты начинаются с последнего записанного простого числа + 2. Поскольку все простые числа после 2 нечетные, это также гарантированно будет следующее нечетное значение. Кандидаты увеличиваются на 2, чтобы пропустить четные числа.

4. , чтобы определить, является ли кандидат простым, деление на ранее записанные простые числа (но только до square root кандидата) .

    static Set<Integer> primes = new LinkedHashSet<>() {
        {   // seed the first two primes.
            add(2);
            add(3);
        }
    };

    // last recorded prime
    static int lastPrime = 3;

    public static boolean isPrime(int val) {
        for (int candidate = lastPrime+2; candidate <= val; candidate += 2) {
           int max = (int)(Math.sqrt(candidate)) + 1;
            for (int p : primes) {
                // if candidate is divisible by any prime, then discontinue
                // testing and move on to next candidate via outer loop
                if (candidate % p == 0) {
                    break;
                }
                // if the limit has been reached, then a prime has been
                // found, so add to list of primes and continue with
                // next candidate.  Only check up tot he square root of the candidate.
                if (p >= max) {
                    // add new found prime to list
                    primes.add(candidate);
                    lastPrime = candidate;
                    break;
                }
            }
        }
        // Now check the newly built (if required) hash set to see if the passed value
        // is in the list.
        return primes.contains(val);
    }

Answer 3

Вот мой подход к решению.

1) Сначала создайте очень простой метод, чтобы проверить, является ли число простым или нет. См. Ниже:

public static boolean checkPrime(int number) {
    if (number <= 1) {
        return false;
    }
    System.out.println(number);

    for (int i=2; i <= Math.sqrt(number); i++) {
        if(number % i == 0) {
            System.out.println(i);
            return false;
        } 
    }
    return true;

}

2) Создайте другой метод, который будет l oop через ваш массив, и вызовите вышеуказанный метод:

public static int numOfPrimesInArray(int[] arr){
    int counter = 0;
    for (int num: arr){
        if (!checkPrime(num)) counter++;
    }
    return counter;
}

3) Затем просто вызовите его из основного Метод:

public static void main(String[] args){
    int[] nums = {1,2,3,5,6,7,8,9,10};
    int nonprimes = numOfPrimesInArray(nums);
    System.out.println(nonprimes);
}

Если я не допустил ошибок при написании этого плеча, укажите количество не простых чисел в вашем массиве.