Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Given an array arr[] of N positive integers. The task is to write a program to count the number of prime elements in the given array.
Examples:
Input: arr[] = {1, 3, 4, 5, 7}
Output: 3
There are three primes, 3, 5 and 7
Input: arr[] = {1, 2, 3, 4, 5, 6, 7}
Output: 4
Naive Approach: A simple solution is to traverse the array and keep checking for every element if it is prime or not and keep the count of the prime elements at the same time.
Efficient Approach: Generate all primes upto maximum element of the array using sieve of Eratosthenes and store them in a hash. Now traverse the array and find the count of those elements which are prime using the hash table.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int primeCount(int arr[], int n)
{
int max_val = *max_element(arr, arr+n);
vector<bool> prime(max_val + 1, true);
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= max_val; p++) {
if (prime[p] == true) {
for (int i = p * 2; i <= max_val; i += p)
prime[i] = false;
}
}
int count = 0;
for (int i = 0; i < n; i++)
if (prime[arr[i]])
count++;
return count;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << primeCount(arr, n);
return 0;
}
Java
import java.util.Arrays;
import java.util.Vector;
class GFG
{
static int primeCount(int arr[], int n)
{
int max_val = Arrays.stream(arr).max().getAsInt();
Boolean[] prime = new Boolean[max_val + 1];
for (int i = 0; i < max_val + 1; i++)
{
prime[i] = true;
}
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= max_val; p++)
{
if (prime[p] == true)
{
for (int i = p * 2; i <= max_val; i += p)
{
prime[i] = false;
}
}
}
int count = 0;
for (int i = 0; i < n; i++)
{
if (prime[arr[i]])
{
count++;
}
}
return count;
}
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = arr.length;
System.out.println(primeCount(arr, n));
}
}
Python3
from math import sqrt
def primeCount(arr, n):
max_val = arr[0];
for i in range(len(arr)):
if(arr[i] > max_val):
max_val = arr[i]
prime =[ True for i in range(max_val + 1)]
prime[0] = False
prime[1] = False
k = int(sqrt(max_val)) + 1
for p in range(2, k, 1):
if (prime[p] == True):
for i in range(p * 2, max_val + 1, p):
prime[i] = False
count = 0
for i in range(0, n, 1):
if (prime[arr[i]]):
count += 1
return count
if __name__ == '__main__':
arr = [1, 2, 3, 4, 5, 6, 7]
n = len(arr)
print(primeCount(arr, n))
C#
using System;
using System.Linq;
class GFG
{
static int primeCount(int []arr, int n)
{
int max_val = arr.Max();
Boolean[] prime = new Boolean[max_val + 1];
for (int i = 0; i < max_val + 1; i++)
{
prime[i] = true;
}
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= max_val; p++)
{
if (prime[p] == true)
{
for (int i = p * 2; i <= max_val; i += p)
{
prime[i] = false;
}
}
}
int count = 0;
for (int i = 0; i < n; i++)
{
if (prime[arr[i]])
{
count++;
}
}
return count;
}
public static void Main()
{
int []arr = {1, 2, 3, 4, 5, 6, 7};
int n = arr.Length;
Console.WriteLine(primeCount(arr, n));
}
}
PHP
<?php
function primeCount($arr, $n)
{
$max_val = max($arr);
$prime = array_fill(0, $max_val + 1, true);
$prime[0] = false;
$prime[1] = false;
for ($p = 2; $p * $p <= $max_val; $p++)
{
if ($prime[$p] == true)
{
for ($i = $p * 2;
$i <= $max_val; $i += $p)
$prime[$i] = false;
}
}
$count = 0;
for ($i = 0; $i < $n; $i++)
if ($prime[$arr[$i]])
$count++;
return $count;
}
$arr = array(1, 2, 3, 4, 5, 6, 7 );
$n = sizeof($arr);
echo primeCount($arr, $n);
?>
Javascript
<script>
function primeCount(arr, n)
{
let max_val = arr.sort((a, b) => b - a)[0];
let prime = new Array(max_val + 1).fill(true);
prime[0] = false;
prime[1] = false;
for (let p = 2; p * p <= max_val; p++)
{
if (prime[p] == true)
{
for (let i = p * 2;
i <= max_val; i += p)
prime[i] = false;
}
}
let count = 0;
for (let i = 0; i < n; i++)
if (prime[arr[i]])
count++;
return count;
}
let arr = new Array(1, 2, 3, 4, 5, 6, 7 );
let n = arr.length;
document.write(primeCount(arr, n));
</script>
Last Updated :
01 Sep, 2022
Like Article
Save Article
мой код дает все простие числа массива но мне нужно найти количество простых чисел каждого отдельно взятого елемента масива…
Примеры:
Входные данные
5 –» 1 2 3 4 5
Результат работы
0 0 1 2 2
Входные данные
11 –» 2 3 5 7 11 13 17 19 23 29 31
Результат работы
0 1 2 3 4 5 6 7 8 9 10
```
#include <iostream>
int main()
{
int n;
std::cin >> n;
int arr[100];
for (int i = 0; i < n; i++)
{
std::cin >> arr[i];
}
std::cout << "N of primes:";
for (int i = 0; i < n ; i++)
{
for (int j = 2; j <= arr[i] / 2; j++)
{
if (arr[i] % j == 0 && arr[i] != j)
{
arr[i] = 0;
break;
}
}
if (arr[i] != 0)
{
std::cout << arr[i] << " ";
}
}
}
```
я начинающий в C++ поэтому мне нужны простые решение задачи
спасибо заранее!
задан 25 июн 2020 в 19:39
Я добавил в код комментарии, чтобы было понятнее.
#include <iostream>
int main(){
// заведем переменную, в которой будем хранить кол-во простых чисел
long long counter = 0;
long long n; std::cin >> n;
// считаем количество вводимых чисел
for(long long i = 0; i < n; ++i){
// будем считывать N простых чисел и проверять их на простоту. Переменна flag нужна как переключатель - простое число или нет
bool flag = true;
long long tmp; std::cin >> tmp;
// выведем счетчик
std::cout << counter << " ";
// проверка на простоту
if(tmp == 1) continue; // 1 - не простое число, уходим на новую итерацию
for(long long d = 2; d * d <= tmp; d++){
if(tmp % d == 0) flag = false; // если число не простое, не будем увеличиваь счетчик
}
if(flag) counter++;
}
}
ответ дан 25 июн 2020 в 20:01
NosorogNosorog
461 серебряный знак6 бронзовых знаков
7
```
#include <iostream>
int main() {
unsigned int n, count = 0, num;
std::cin >> n;
int arr[100];
for (int i = 0; i < n; ++i) {
std::cin >> arr[i];
}
for (int i = 0; i < n; ++i) {
std::cout << count << " ";
num = arr[i];
if (num == 2)
count++;
if (num < 2 || num % 2 == 0)
continue;
int j;
for (j = 2; j < num; j++)
if (num % j == 0)
break;
if (j * j > num)
count++;
}
}
```
как решить проблему когда вводятся 10 чисел например –» 3 5 7 11 13 17 19 23 29 31
Правильный ответ был 1 2 3 4 5 6 7 8 9 10
сейчас программа дает ответ 0 1 2 3 4 5 6 7 8 9
ответ дан 25 июн 2020 в 22:42
Как найти количество простых чисел в массиве?
Необходимо реализовать алгоритм, который будет считать количество простых чисел в выданном массиве. Ограничение по памяти 256 Мб, по времени 1 секунда.
Формат ввода
- В первой строке содержится единственное число 1 ≤ n ≤ 1000 – размер выборки
- Во второй строке содержится n целых чисел 2 ≤ ai ≤ 1012 – выборка
Sample Input 3:
5
15 17 2 8 15
Sample Output 3:
2
Проблема в верхнем пределе возможного числа в выборке, когда оно действительно приближается к 12 нулям выпадают исключения типа MemoryError, а если решить и эту проблему, то алгоритм не укладывается в необходимую 1 секунду.
Пытался использовать решето Эратосфена в различных реализациях, но ничего не вышло. Подозреваю, что возможно решить с помощью генераторов, но моих скиллов пока не хватает.
-
Вопрос заданболее года назад
-
379 просмотров
Тут не нужно решето. Надо просто отдельно проверить каждое число на простоту.
Подсказка: Если число не простое, то у него есть простой делитель не больше корня (потому что иначе – есть хотя бы 2 делителя и они оба больше корня и их произведение уже больше самого числа).
Пригласить эксперта
Непонятно, откуда у вас MemoryError. Если исходная выборка размещена в памяти, и ей хватило там места, то на что у вас расходуется память? Вам ведь не надо запоминать все полученные простые числа. Вы берете их по одному и просто выясняете – простое оно или нет.
Вот со временем – да, если у вас действительно большие числа и их к тому-же много – ну тогда переборный алгоритм быстрый не будет. Поэтому ограничение в 1 сек. – это просто какая-то мягко говоря странность, если не указывать, а какие именно числа в вашей последовательности. Для 1000 чисел, всех лежащих в диапазоне от 0 до 1001 – это одно, а для лежащих в диапазоне от 10**12-1000 до 10**12 – это совсем разное время работы.
Задача явно требует расчёта этих самых простых чисел и переиспользования списка.
Так что сначала генерим список простых чисел во вменяемом диапазоне, скажем, до тысячи. Берём очередное число. Если оно меньше квадрата самого большого из простых чисел списка, проверяем, что оно делится или не делится на какое-то из них. А если больше – просто перед проверкой догенерируем в список простые числа до нужного порога. При этом используем повторно ту же самую процедуру проверки числа на простоту.
Нет, конечно, можно и сразу нагенерить простых до миллиона, но смысл?
-
Показать ещё
Загружается…
18 мая 2023, в 17:43
3000 руб./за проект
18 мая 2023, в 17:40
2000 руб./за проект
18 мая 2023, в 17:26
1500 руб./за проект
Минуточку внимания
Раздел:
Задачи /
Простейшие /
Как определить простое число
|
|
Основы программирования Каждый профессионал когда-то был чайником. Наверняка вам знакомо состояние, когда “не знаешь как начать думать, чтобы до такого додуматься”. Наверняка вы сталкивались с ситуацией, когда вы просто не знаете, с чего начать. Эта книга ориентирована как раз на таких людей, кто хотел бы стать программистом, но совершенно не знает, как начать этот путь. Подробнее… |
Условие задачи 2.30
Задача 2.30
Дан одномерный массив А, состоящий из натуральных чисел. Вывести на экран количество простых чисел в массиве.
Для начала напомню, что такое простые числа.
Простое число – это натуральное число, которое имеет ровно два различных натуральных делителя – единицу и самого себя.
То есть если число делится без остатка только на 1 и на самого себя, то такое число является простым.
Например, простыми числами являются 2, 3, 5 и т.п.
А вот 4 уже не является простым, так как делится без остатка не только на 1 и 4, но ещё и на 2.
Если вы подзабыли, что такое натуральное число, то см. здесь.
А теперь перейдём к задаче. По сути нам нужна программа, определяющая простые числа. А уж
перебрать элементы массива в
цикле и проверить их значения – это дело техники. Заодно мы можем не только подсчитать, но и вывести на экран простые числа массива.
Как определить простое число в Паскале
Алгоритм решения с подробным разбором приведу на Паскале. Решение на С++ можете посмотреть в примере программы на С++.
ВАЖНО!
На этом многие могут ошибиться. В определении сказано, что простое число имеет
ровно два различных делителя. Следовательно, число 1 не является простым (также не является простым, так как ноль можно делить на любые числа).
Проверять, является ли число простым, будем с помощью функции, которую сами и создадим. Эта функция будет возвращать TRUE, если число простое.
В функции сначала будем проверять, не является ли число меньше двух. Если да, то это уже не простое число. Если же число равно 2 или 3, то оно является однозначно простым и делать какие-то дополнительные проверки не требуется.
А вот если число N будет больше трёх, то в этом случае в цикле будем перебирать все возможные делители, начиная от 2 до (N-1). Если на какой-то делитель число N делится без остатка, значит, это тоже не простое число. В этом случае мы прерываем цикл (потому что проверять дальше нет смысла), а функция возвращает FALSE.
Проверять, делится ли число на самоё себя нет смысла (поэтому цикл длится только до N-1).
Саму функцию здесь приводить не буду – посмотрите её в примерах программ.
Решение задачи 2.30 на Паскале
program mytask;
//****************************************************************
// КОНСТАНТЫ
//****************************************************************
const
COUNT = 100; //Количество элементов в массиве
//****************************************************************
// ФУНКЦИИ И ПРОЦЕДУРЫ
//****************************************************************
//****************************************************************
// Проверяет, является ли число простым
// ВХОД : N - число
// ВЫХОД : TRUE - число N простое, FALSE - не простое
//****************************************************************
function IsPrimeNumber(N : WORD) : boolean;
var i : WORD;
begin
Result := TRUE;
case N of
0..3 :
begin
if N < 2 then Result := FALSE; //Не простое число
Exit;
end;
end;
for i := 2 to (N-1) do
if (N mod i) = 0 then //Не простое число
begin
Result := FALSE;
Break;
end;
end;
var i : WORD;
X : WORD = 0;
A : array[1..COUNT] of WORD;
//****************************************************************
// ОСНОВНАЯ ПРОГРАММА
//****************************************************************
begin
//Заполнить массив числами
for i := 1 to COUNT do
A[i] := i;
//Подсчитать и выбрать простые числа из массива
for i := 1 to COUNT do
if IsPrimeNumber(A[i]) then
begin
Inc(X);
Write(A[i], ' ');
end;
WriteLn(#10#13'Number of Prime numbers = ', X);
WriteLn('The end. Press ENTER...');
ReadLn;
end.
Решение задачи 2.30 на С++
#include <cstdlib>
#include <iostream>
using namespace std;
//****************************************************************
// КОНСТАНТЫ
//****************************************************************
const int COUNT = 100; //Количество элементов в массиве
//****************************************************************
// ФУНКЦИИ И ПРОЦЕДУРЫ
//****************************************************************
//****************************************************************
// Проверяет, является ли число простым
// ВХОД : N - число
// ВЫХОД : TRUE - число N простое, FALSE - не простое
//****************************************************************
bool IsPrimeNumber(int N)
{
bool Res = true;
switch (N)
{
case 0 : Res = false; break;
case 1 : Res = false; break;
case 2 : Res = true; break;
case 3 : Res = true; break;
default :
for (int i = 2; i < N; i++)
if (0 == (N % i)) //Не простое число
{
Res = false;
break;
}
}
return(Res);
}
//****************************************************************
// ОСНОВНАЯ ПРОГРАММА
//****************************************************************
int main(int argc, char *argv[])
{
int A[COUNT];
int X = 0;
//Заполнить массив числами
for (int i = 0; i < COUNT; i++)
A[i] = i;
//Подсчитать и выбрать простые числа из массива
for (int i = 0; i < COUNT; i++)
if (IsPrimeNumber(A[i]))
{
X++;
cout << A[i] << " ";
};
cout << endl << "Number of Prime numbers = " << X << endl;
system("PAUSE");
return EXIT_SUCCESS;
}
|
|
Как стать программистом 2.0
Эта книга для тех, кто хочет стать программистом. На самом деле хочет, а не просто мечтает. И хочет именно стать программистом с большой буквы, а не просто научиться кулебякать какие-то примитивные программки… |
|
|
Помощь в технических вопросах
Помощь студентам. Курсовые, дипломы, чертежи (КОМПАС), задачи по программированию: Pascal/Delphi/Lazarus; С/С++; Ассемблер; языки программирования ПЛК; JavaScript; VBScript; Fortran; Python и др. Разработка (доработка) ПО ПЛК (предпочтение – ОВЕН, CoDeSys 2 и 3), а также программирование панелей оператора, программируемых реле и других приборов систем автоматизации. |
|
0 / 0 / 0 Регистрация: 09.06.2015 Сообщений: 16 |
|
|
1 |
|
Найти количество простых чисел в массиве30.05.2016, 07:36. Показов 10251. Ответов 1
Дано N мерное массивное число. Есть ли среди массивом простое число? Если есть то нужно вывести число этих элементов.
0 |
|
Programming Эксперт 94731 / 64177 / 26122 Регистрация: 12.04.2006 Сообщений: 116,782 |
30.05.2016, 07:36 |
|
Ответы с готовыми решениями: Найти количество простых чисел в массиве Найти в одномерном массиве, состоящем из N целых чисел, количество простых элементов Общая постановка задания: Используя динамический массив и… Найти в массиве количество простых чисел,больших суммы цифр первого числа Найти в заданном одномерном массиве количество простых чисел, используя сортировку простым включением 1 |
|
lawr 385 / 279 / 478 Регистрация: 09.05.2014 Сообщений: 769 |
||||
|
30.05.2016, 10:33 |
2 |
|||
|
Решение
1 |
Сообщение было отмечено Shqrr как решение
|
IT_Exp Эксперт 87844 / 49110 / 22898 Регистрация: 17.06.2006 Сообщений: 92,604 |
30.05.2016, 10:33 |
|
2 |
