찾다
백엔드 개발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으로 문의하시기 바랍니다. 삭제
C의 미래 : 적응 및 혁신C의 미래 : 적응 및 혁신Apr 27, 2025 am 12:25 AM

C의 미래는 병렬 컴퓨팅, 보안, 모듈화 및 AI/기계 학습에 중점을 둘 것입니다. 1) 병렬 컴퓨팅은 코 루틴과 같은 기능을 통해 향상 될 것입니다. 2)보다 엄격한 유형 검사 및 메모리 관리 메커니즘을 통해 보안이 향상 될 것입니다. 3) 변조는 코드 구성 및 편집을 단순화합니다. 4) AI 및 머신 러닝은 C가 수치 컴퓨팅 및 GPU 프로그래밍 지원과 같은 새로운 요구에 적응하도록 촉구합니다.

C의 장수 : 현재 상태를 조사합니다C의 장수 : 현재 상태를 조사합니다Apr 26, 2025 am 12:02 AM

C는 효율적이고 유연하며 강력한 특성으로 인해 현대 프로그래밍에서 여전히 중요합니다. 1) C는 시스템 프로그래밍, 게임 개발 및 임베디드 시스템에 적합한 객체 지향 프로그래밍을 지원합니다. 2) 다형성은 C의 하이라이트이며, 기본 클래스 포인터 또는 참조를 통해 도출 된 클래스 방법으로의 호출을 허용하여 코드의 유연성과 확장 성을 향상시킵니다.

C# vs. C 성능 : 벤치마킹 및 고려 사항C# vs. C 성능 : 벤치마킹 및 고려 사항Apr 25, 2025 am 12:25 AM

C#과 C의 성능 차이는 주로 실행 속도 및 리소스 관리에 반영됩니다. 1) C는 일반적으로 하드웨어에 더 가깝고 쓰레기 수집과 같은 추가 오버 헤드가 없기 때문에 수치 계산 및 문자열 작업에서 더 잘 수행됩니다. 2) C#은 다중 스레드 프로그래밍에서 더 간결하지만 성능은 C보다 약간 열등합니다. 3) 선택해야 할 언어는 프로젝트 요구 사항 및 팀 기술 스택을 기반으로 결정해야합니다.

C : 죽어 가거나 단순히 진화하고 있습니까?C : 죽어 가거나 단순히 진화하고 있습니까?Apr 24, 2025 am 12:13 AM

c is nontdying; it'sevolving.1) c COMINGDUETOITSTIONTIVENICICICICINICE INPERFORMICALEPPLICATION.2) thelugageIscontinuousUllyUpdated, witcentfeatureslikemodulesandCoroutinestoimproveusActionalance.3) despitechallen

C 현대 세계에서 : 응용 및 산업C 현대 세계에서 : 응용 및 산업Apr 23, 2025 am 12:10 AM

C는 현대 세계에서 널리 사용되고 중요합니다. 1) 게임 개발에서 C는 Unrealengine 및 Unity와 같은 고성능 및 다형성에 널리 사용됩니다. 2) 금융 거래 시스템에서 C의 낮은 대기 시간과 높은 처리량은 고주파 거래 및 실시간 데이터 분석에 적합한 첫 번째 선택입니다.

C XML 라이브러리 : 옵션 비교 및 ​​대조C XML 라이브러리 : 옵션 비교 및 ​​대조Apr 22, 2025 am 12:05 AM

C : Tinyxml-2, Pugixml, XERCES-C 및 RapidXML에는 4 개의 일반적으로 사용되는 XML 라이브러리가 있습니다. 1. TINYXML-2는 자원이 제한적이고 경량이지만 제한된 기능을 가진 환경에 적합합니다. 2. PugixML은 빠르며 복잡한 XML 구조에 적합한 XPath 쿼리를 지원합니다. 3.xerces-c는 강력하고 DOM 및 SAX 해상도를 지원하며 복잡한 처리에 적합합니다. 4. RapidXML은 성능에 중점을두고 매우 빠르게 구문 분석하지만 XPath 쿼리를 지원하지는 않습니다.

C 및 XML : 관계와 지원 탐색C 및 XML : 관계와 지원 탐색Apr 21, 2025 am 12:02 AM

C는 XML과 타사 라이브러리 (예 : TinyXML, Pugixml, Xerces-C)와 상호 작용합니다. 1) 라이브러리를 사용하여 XML 파일을 구문 분석하고 C- 처리 가능한 데이터 구조로 변환하십시오. 2) XML을 생성 할 때 C 데이터 구조를 XML 형식으로 변환하십시오. 3) 실제 애플리케이션에서 XML은 종종 구성 파일 및 데이터 교환에 사용되어 개발 효율성을 향상시킵니다.

C# vs. C : 주요 차이점과 유사성 이해C# vs. C : 주요 차이점과 유사성 이해Apr 20, 2025 am 12:03 AM

C#과 C의 주요 차이점은 구문, 성능 및 응용 프로그램 시나리오입니다. 1) C# 구문은 더 간결하고 쓰레기 수집을 지원하며 .NET 프레임 워크 개발에 적합합니다. 2) C는 성능이 높고 시스템 프로그래밍 및 게임 개발에 종종 사용되는 수동 메모리 관리가 필요합니다.

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 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

SublimeText3 Linux 새 버전

SublimeText3 Linux 새 버전

SublimeText3 Linux 최신 버전

Eclipse용 SAP NetWeaver 서버 어댑터

Eclipse용 SAP NetWeaver 서버 어댑터

Eclipse를 SAP NetWeaver 애플리케이션 서버와 통합합니다.

VSCode Windows 64비트 다운로드

VSCode Windows 64비트 다운로드

Microsoft에서 출시한 강력한 무료 IDE 편집기

ZendStudio 13.5.1 맥

ZendStudio 13.5.1 맥

강력한 PHP 통합 개발 환경

SublimeText3 중국어 버전

SublimeText3 중국어 버전

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