찾다
백엔드 개발C++C++로 작성되었으며, 주어진 범위에서 접두어와 소수의 개수를 찾습니다.

C++로 작성되었으며, 주어진 범위에서 접두어와 소수의 개수를 찾습니다.

이 기사에서는 주어진 양의 정수 배열 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
이 기사는 tutorialspoint에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제
(超详细)VScode中配置C语言环境的方法(超详细)VScode中配置C语言环境的方法Dec 05, 2022 pm 07:05 PM

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

c语言中node是什么意思c语言中node是什么意思Jul 06, 2022 pm 03:51 PM

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

c语言怎么将数字转换成字符串c语言怎么将数字转换成字符串Jan 04, 2023 pm 03:20 PM

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

c语言开根号运算符是什么c语言开根号运算符是什么Mar 06, 2023 pm 02:39 PM

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

c语言数组如何初始化c语言数组如何初始化Jan 04, 2023 pm 03:36 PM

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语言合法标识符的要求是什么c语言合法标识符的要求是什么Aug 27, 2020 pm 01:47 PM

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

c语言中源文件编译后生成什么文件c语言中源文件编译后生成什么文件Nov 23, 2022 pm 07:44 PM

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

c语言怎么计算n的阶乘c语言怎么计算n的阶乘Jan 04, 2023 pm 03:18 PM

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...”。

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

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

뜨거운 도구

안전한 시험 브라우저

안전한 시험 브라우저

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

SublimeText3 Linux 새 버전

SublimeText3 Linux 새 버전

SublimeText3 Linux 최신 버전

SublimeText3 중국어 버전

SublimeText3 중국어 버전

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

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 Mac 버전

SublimeText3 Mac 버전

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