이 기사에서는 주어진 양의 정수 배열 arr[ ]에서 여러 소수 접두사 합을 찾고 범위 쿼리 L, R을 수행해야 합니다. 여기서 L은 접두사 합[ ] 배열입니다. 초기 인덱스 값 arr[L], R은 우리가 찾아야 하는 접두어 합계의 수입니다.
접두사 합계 배열을 채우기 위해 인덱스 L부터 인덱스 R까지 시작하고 주어진 배열의 마지막 요소에 현재 값을 추가합니다. 다음은 문제의 예입니다.
Input : arr[ ] = { 3, 5, 6, 2, 4 } L = 1, R = 3 Output : 3 Explanation : prefixsum[ 0 ] = arr[ L ] = 5 prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 2 ] = 11 prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 3 ] = 13 In prefixsum[ ] array all three 5, 11 and 13 are prime numbers in prefix sum array in given range. Input : arr[ ] = { 6, 10, 5, 8, 11 } L = 0, R = 3 Output : 1 Explanation : prefixsum[ 0 ] = arr[ L ] = 6 prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 1 ] = 16 prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 2 ] = 21 prefixsum[ 3 ] = prefixsum[ 2 ] + arr[ 3 ] = 29 In prefixsum[ ] array only 29 is the prime number in prefix sum array given range.
솔루션을 찾는 방법
이 문제에서 우리는 새로운 배열 prefixsum[ ]을 만들고 배열의 이전 요소와 현재 요소를 추가하여 접두사 sum을 추가해야 한다고 말할 수 있습니다. 주어진 배열 요소의 요소입니다. 접두사 합계 배열의 첫 번째 요소는 지정된 배열의 인덱스 L에 있는 값이 됩니다.
L에서 R까지 루프를 실행해야 합니다. 여기서 L과 R은 주어진 배열입니다. 그런 다음 prefixsum[ ] 배열의 요소를 확인하고 발견된 각 소수의 개수를 늘립니다.
Example
#include<bits/stdc++.h> using namespace std; vector < bool > checkprime (int *arr, int n, int MAX){ vector < bool > p (n); bool Prime_val[MAX + 1]; for (int i = 2; i < MAX; i++) Prime_val[i] = true; Prime_val[1] = false; for (int p = 2; p * p <= MAX; p++){ // If prime[p] is not changed, then // it is a prime if (Prime_val[p] == true){ // Update all multiples of p for (int i = p * 2; i <= MAX; i += p) Prime_val[i] = false; } } for (int i = 0; i < n; i++){ if (Prime_val[arr[i]]) p[i] = true; else p[i] = false; } return p; } int main (){ int arr[] = { 2, 3, 4, 7, 9, 10 }; int s1 = sizeof (arr) / sizeof (arr[0]);//size of given array int L = 1, R = 3, s2 = R - L + 1; int prefixsum[s2]; int count = 0; prefixsum[0] = arr[L]; for (int i = L + 1, j = 1; i <= R && j < s1; i++, j++){ prefixsum[j] = prefixsum[j - 1] + arr[i]; } vector < bool > isprime = checkprime (prefixsum, s2, prefixsum[s2 - 1]); for (int i = 0; i < s2; i++) { if (isprime[i] == 1) count++; } cout <<"Number of prefix sum prime in given range query: " << count; return 0; }
Output
Number of prefix sum prime in given range query: 2
위 코드 설명
이 코드에서는 prefixsum[ ] 배열을 만들고 prefixsum[ ] 배열의 이전 요소와 현재 요소의 합으로 채웁니다. 주어진 배열. 그런 다음 접두사 배열의 모든 숫자가 소수인지 아닌지 확인합니다. 여기서는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하여 소수를 확인합니다. 마지막으로 각 소수의 개수를 늘리고 결과를 표시합니다.
결론
이 기사에서는 순진한 접근 방식을 적용하고 에라토스테네스의 체를 사용하여 접두사 합 배열에서 소수를 찾았습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.
위 내용은 C++로 작성되었으며, 주어진 범위에서 접두어와 소수의 개수를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

VScode中怎么配置C语言环境?下面本篇文章给大家介绍一下VScode配置C语言环境的方法(超详细),希望对大家有所帮助!

在C语言中,node是用于定义链表结点的名称,通常在数据结构中用作结点的类型名,语法为“struct Node{...};”;结构和类在定义出名称以后,直接用该名称就可以定义对象,C语言中还存在“Node * a”和“Node* &a”。

c语言将数字转换成字符串的方法:1、ascii码操作,在原数字的基础上加“0x30”,语法“数字+0x30”,会存储数字对应的字符ascii码;2、使用itoa(),可以把整型数转换成字符串,语法“itoa(number1,string,数字);”;3、使用sprintf(),可以能够根据指定的需求,格式化内容,存储至指针指向的字符串。

在c语言中,没有开根号运算符,开根号使用的是内置函数“sqrt()”,使用语法“sqrt(数值x)”;例如“sqrt(4)”,就是对4进行平方根运算,结果为2。sqrt()是c语言内置的开根号运算函数,其运算结果是函数变量的算术平方根;该函数既不能运算负数值,也不能输出虚数结果。

C语言数组初始化的三种方式:1、在定义时直接赋值,语法“数据类型 arrayName[index] = {值};”;2、利用for循环初始化,语法“for (int i=0;i<3;i++) {arr[i] = i;}”;3、使用memset()函数初始化,语法“memset(arr, 0, sizeof(int) * 3)”。

c语言合法标识符的要求是:1、标识符只能由字母(A~Z, a~z)、数字(0~9)和下划线(_)组成;2、第一个字符必须是字母或下划线,不能是数字;3、标识符中的大小写字母是有区别的,代表不同含义;4、标识符不能是关键字。

c语言编译后生成“.OBJ”的二进制文件(目标文件)。在C语言中,源程序(.c文件)经过编译程序编译之后,会生成一个后缀为“.OBJ”的二进制文件(称为目标文件);最后还要由称为“连接程序”(Link)的软件,把此“.OBJ”文件与c语言提供的各种库函数连接在一起,生成一个后缀“.EXE”的可执行文件。

c语言计算n的阶乘的方法:1、通过for循环计算阶乘,代码如“for (i = 1; i <= n; i++){fact *= i;}”;2、通过while循环计算阶乘,代码如“while (i <= n){fact *= i;i++;}”;3、通过递归方式计算阶乘,代码如“ int Fact(int n){int res = n;if (n > 1)res...”。


핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

안전한 시험 브라우저
안전한 시험 브라우저는 온라인 시험을 안전하게 치르기 위한 보안 브라우저 환경입니다. 이 소프트웨어는 모든 컴퓨터를 안전한 워크스테이션으로 바꿔줍니다. 이는 모든 유틸리티에 대한 액세스를 제어하고 학생들이 승인되지 않은 리소스를 사용하는 것을 방지합니다.

SublimeText3 Linux 새 버전
SublimeText3 Linux 최신 버전

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)
