計算範圍內的素數


難度級別
經常問 谷歌 遠足 庫利扎 Snapchat 雅虎
數學 數字系統

問題陳述

問題“在範圍內計算素數”指出給定了一個範圍[left,right],其中0 <= left <= right <= 10000。 問題陳述要求找出該範圍內的質數總數。 假設會有大量查詢。

left: 4
right:10
2

解釋

5和7是僅有的2個質數。

計算範圍內的素數

left: 6
right:8
1

解釋

7是唯一的質數。

算法

  1. 創建一個 整數 數組和布爾數組 '主要的' 給定最大大小,並使用初始化布爾數組 .
  2. 遍歷布爾數組,並檢查'prime'數組的當前值是否為true。
  3. 然後從當前數組元素開始遍歷,然後將每個數組元素初始化為false,其距離等於當前元素的大小。 這意味著我們將移至當前元素的倍數。
  4. 將prePrime [0]和prePrime [1]設置為0。
  5. 從2遍歷直到最大給定值。
  6. 將值複製到prePrime數組的上一個索引,並檢查prime數組的當前值是否等於true,然後將prePrime的值增加1。
  7. 對於每個查詢,返回prePrime [right]和prePrime [left-1]之差。

解釋

給定範圍內的數字作為起始數字和結束數字。 因此,考慮到此範圍,因為它被所有中間數字填充。 我們已要求找出此範圍內的質數總數。 為此,我們將構建一個prePrime數組,通過該數組我們可以解決最大數量範圍內的任何查詢。 聲明一個給定的最大大小為10000的整數數組,並且使用相同的大小,我們將聲明一個布爾數組,並將其初始化為true值。

從值XNUMX遍歷一個循環,因為我們不能將一個視為素數。 檢查布爾素數數組的每個值的每個值是否等於true,如果發現它為true,則我們將進一步循環遍歷。 我們將從當前數字的兩倍開始,然後移至其倍數,直到達到最大大小的值,然後將每個值初始化為false。 這種方法通常稱為 Eratosthenes篩.

我們將值設置為0th 和1st prePrime數組的值設置為0。因此,我們將從2開始遍歷prePrime和prime數組。 然後我們將prePrime數組的下一個值複製到prePrime數組的前一個值,並檢查prime數組的當前值是否為true,如果為true,則增加prePrime數組的當前元素的值。 對於每個查詢,我們都會收到一個開始編號和一個結束編號。 我們將返回prePrime [right]和prePrime [left-1]的差。 這將是必需的答案。

推薦碼

用C ++實現以計算範圍內的素數

#include<iostream>
#include<stdio.h>
#include<cstring>

using namespace std;

const int MAX = 10000;

int prePrime[MAX + 1];

void PrePrimeFunction ()
{

    bool prime[MAX + 1];
    memset(prime, true, sizeof(prime));

    for (int a = 2; a * a <= MAX; a ++)
    {
        if (prime[a] == true)
        {
            for (int i = a * 2; i <= MAX; i += a)
                prime[i] = false;
        }
    }
    prePrime[0] = prePrime[1] = 0;
    for (int q = 2; q <= MAX; q++)
    {
        prePrime[q] = prePrime[q - 1];
        if (prime[q])
            prePrime[q]++;
    }
}

int solveQuery(int L, int R)
{
    return prePrime[R] - ((L>0) ? prePrime[L - 1] : 0);
}

int main()
{
    PrePrimeFunction();

    int L = 4, R = 10;
    cout << solveQuery(L, R) << endl;

    L = 6, R = 8;
    cout << solveQuery(L, R) << endl;

    return 0;
}
2
1

用Java實現以計算範圍內的素數

import java.util.Arrays;

class PrimeInRange
{

    static final int MAX = 10000;

    static int prePrime[] = new int[MAX + 1];

    static void PrePrimeFunction()
    {

        boolean prime[] = new boolean[MAX + 1];
        Arrays.fill(prime, true);

        for (int a = 2; a * a <= MAX; a++)
        {
            if (prime[a] == true)
            {

                for (int i = a * 2; i <= MAX; i += a)
                    prime[i] = false;
            }
        }

        prePrime[0] = prePrime[1] = 0;

        for (int q = 2; q <= MAX; q++)
        {
            prePrime[q] = prePrime[q - 1];
            if (prime[q])
                prePrime[q]++;
        }
    }

    static int solveQuery(int L, int R)
    {
        return prePrime[R] - ((L>0) ? prePrime[L - 1] : 0);
    }

    public static void main(String[] args)
    {
        PrePrimeFunction();
        int L = 4, R = 10;
        System.out.println(solveQuery(L, R));

        L = 6;
        R = 8;
        System.out.println(solveQuery(L, R));
    }
}
2
1

複雜度分析

時間複雜度

O(n * log(log(n))+ q) 哪裡 “ n” 是數組中元素的數量,並且 “Q” 是查詢數。 因此,這種時間複雜性是由於我們使用了“ Eratosthenes篩”。

空間複雜度

O(1) 因為數組的大小不依賴於輸入,所以它等於一個常量值。 因為需要空間來存儲素數的結果。 由於我們存儲數字是否為質數。