标签: primes

我是一名新的 java 程序员，最近被告知要检查 scala 的并发实现。我认为一个简单的（尽管不是说明并发性的最佳例子）示例可能是让参与者解决埃拉托斯特尼筛法。到目前为止，我已经拼凑了一些东西，但我不确定我要走的方向是否接近正确。这是我当前的代码：

import scala.actors.Actor
import scala.actors.Actor._
import Array._

class PrimeActor(val id: Int) extends Actor {

     //Runs one Prime of the Sieve of Eratosthenes
     def sieve(p: Int, list: Array[Int]) {
       var i = 1
       var place = 0
       while(list contains (i * p)) {
       place = list.indexOf(i * p)
       if (list(place) != 0) 
          list.update(place, 0)
       i += 1
       }
     }

   //Checks to see if there is a higher prime in the list
   //If so, creates a new actor …

我正在尝试打印 2**32 以下的每个素数。现在我正在使用布尔向量构建一个筛子，然后在制作筛子后打印出素数。仅打印 10 亿以内的素数就需要 4 分钟。有没有更快的方法来做到这一点？这是我的代码

#include <iostream>
#include <cstdlib>
#include <vector>
#include <math.h>

using namespace std;

int main(int argc, char **argv){
  long long limit = atoll(argv[1]);
  //cin >> limit;
  long long sqrtlimit = sqrt(limit);

  vector<bool> sieve(limit+1, false);

  for(long long n = 4; n <= limit; n += 2)
    sieve[n] = true;

  for(long long n=3; n <= sqrtlimit; n = n+2){
    if(!sieve[n]){
      for(long long m = n*n; m<=limit; m=m+(2*n))
        sieve[m] = true;
    }
  }

  long long last;
  for(long long …

我知道有多种方法可以找到前 100 个素数，但请帮助我采用我的方法。我发现 的值count正在增加，但由于某种原因while循环条件不适用：

count = 0

while(count <= 20):
    for i in range(2, 20):
        for j in range(2, i):
            if i < j:
                print("The number",i,"is prime")
            elif i % j == 0:
                break
        else:
            print("The number",i,"is prime")
            count = count + 1
            print(count)

我知道这个问题之前已经被回答过，但我不太明白对该问题的解释。

我在 HackerRank 上做了 30 天的代码，其中一个练习是检查一个数字是否是素数。不幸的是，我自己无法做到这一点，所以我在多次尝试后检查了给定的解决方案。即使在查看了解决方案之后，我也无法理解其中一行：

// Check for primality using odd numbers from 3 to sqrt(n)
for(int i = 3; i <= sqrt(n); i += 2){
    // n is not prime if it is evenly divisible by some 'i' in this range
    if( n % i == 0 ){ 
        isPrime = false;
    }
}

为什么sqrt(n)在for循环中使用？

我编写的程序循环遍历一个范围并找到素数和回文数。作为学习 asyncio 的一部分，我尝试使用 async 重新构建它。但结果并不好。这里异步代码比同步代码花费的时间要长得多。

同步代码

import math
import time


def prime(n):
    limit=int(math.sqrt(n))
    for j in range(2,limit):
        if(n%j==0):
            return 0
    return 1


def pallindrome(n):
    n=str(n)
    m=n[::-1]
    if(m==n):
        return 1
    return  0


a, b, c = 999999999, 9999999, 0
start = time.time()

for i in range(a, b, -1): 
    if(pallindrome(i)):  
        if(prime(i)):
            c+=1
            print(i)
    if(c==20):
        break
print("took --> ", time.time()-start)

结果 ：

999727999
999686999
999676999
999565999
999454999
999434999
999272999
999212999
999070999
998979899
998939899
998898899
998757899
998666899
998565899
998333899
998282899
998202899
998171899
998121899
took …

所以我必须为学校编写代码。我做到了，但我的输出不是他们要求的方式。这段代码给出了两个不同数字之间的素数。所以我必须按行打印这些数字。但是，是的，下面的答案之间有零，你可以明白我的意思。我怎样才能解决这个问题？

#include <stdio.h>

int is_prime (int number)
{
    int is_prime= 1, i;

    if (number < 2)
    {
        is_prime = 0;
    }
    else
    {
        for(i = 2; (i * i) <= number; i++)
        {
            if ((number % i) == 0)
            {
                is_prime = 0;
                break;
            }
            else
            {
                is_prime = 1;
            }
        }
    }
    return is_prime;
}

int main (void)
{
    int lower_limit, upper_limit, i;

    scanf("%d\n%d", &lower_limit, &upper_limit);

    for(i = lower_limit; i <= upper_limit; i++)
    {
        if (is_prime (i))
        {
            printf("\n%d", …

尝试使用 C++11 std::uniform_int_distribution生成[2,2147483647] 范围内的随机素数p。

有人评论说这种方法可能不正确：

这个p均匀分布在所有素数 <= 2^31 - 1 的集合上并不是立即显而易见的。无论均匀性和偏差保证随机数生成器具有什么，它们都指范围内的所有整数，但代码是“筛分”只是从中取出素数。

然而，从另一篇类似的SO文章中，它指出

只要输入的随机数在该范围内均匀分布，则该方法选择的素数也将均匀分布在该范围内的素数中。

问题

这段代码真的能正确生成随机素数吗？

https://onlinegdb.com/FMzz78LBq

#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <time.h>
#include <random>


int isPrimeNumber (int num)
{
  if (num == 1) return 0;

  for (int i = 2; i <= sqrt (num); i++)
  {
      if (num % i == 0)
      {
        // not prime
        return 0;
      }
  }

  // prime
  return 1;
}

int main ()
{
  std::random_device rd;
  std::mt19937 …

尝试编写一个程序来检查一个数字是否为素数。写了下面的代码，但不明白为什么我有两行输出：

num = int(input("Provide number to check if prime: "))
if num <=1:
    print("Invalid choice, try again")
    num = int(input("Provide number to check if prime: "))

for i in range(2,num):
    if num% i ==0:
        print("Number is not prime")
        break
    if num %i !=0:
        print("Number is prime")

我的输出是：

Provide number to check if prime: 15
Number is prime
Number is not prime

所以我正在尝试学习 lisp，我想出了一个简单的程序来帮助我学习它，它只是一个检查素数的程序。一开始它起作用了：

(dotimes (i 100)
    (let ((devisors 0)) 
        (if (> i 2) 
            (progn
            (dotimes (j (+ (/ i 2) 1))
            (if (> j 1) 
                (if (= (rem i j) 0) (setq devisors 1) )
            ))
            (if (= devisors 0) (print i))
            )
        )
    )
)

然后我尝试将素数检查抽象为一个函数，并编写了以下代码：

(defun isprime (num) 
    (defvar devisors 0)
    (dotimes (j (+ (/ num 2) 1))
    (if (> j 1) 
        (if (= (rem num j) 0) (setq devisors 1) )
    ))
    (if (= devisors 0) num 0) …

我在 NumPy 中实现了自己的埃拉托斯特尼筛法。我相信你们都知道它是为了找到一个数字以下的所有素数，所以我不会进一步解释。

代码：

import numpy as np\n\ndef primes_sieve(n):\n    primes = np.ones(n+1, dtype=bool)\n    primes[:2] = False\n    primes[4::2] = False\n    for i in range(3, int(n**0.5)+1, 2):\n        if primes[i]:\n            primes[i*i::i] = False\n\n    return np.where(primes)[0]\n

正如你所看到的，我已经做了一些优化，首先除了 2 之外所有素数都是奇数，所以我将 2 的所有倍数设置为False且仅是暴力奇数。

其次，我只循环遍历直到平方根下限的数字，因为平方根之后的所有合数都会因平方根以下素数的倍数而被消除。

但这不是最佳的，因为它循环遍历低于限制的所有奇数，并且并非所有奇数都是质数。随着数字的增大，素数变得更加稀疏，因此存在大量冗余迭代。

因此，如果候选列表是动态更改的，以这样的方式，已经识别的合数甚至不会被迭代，因此只有质数被循环，不会有任何浪费的迭代，因此算法将是最优的。

我写了一个优化版本的粗略实现：

def primes_sieve_opt(n):\n    primes = np.ones(n+1, dtype=bool)\n    primes[:2] = False\n    primes[4::2] = False\n    limit = int(n**0.5)+1\n    i = 2\n    while i < limit:\n        primes[i*i::i] = False\n        i += 1 + …