标签: primes

如何找到小于n的最大素数,其中n≤10？请帮我找一个高效的算法.

for(j=n;j>=2;j--) {
  if(j%2 == 1) {
    double m = double(j);
    double a = (m-1)/6.0;
    double b = (m-5)/6.0;
    if( a-(int)a == 0 || b-(int)b == 0 ) {
      printf("%llu\n",j);
      break;
    }
  }
}

我使用这种方法,但这对于n> 10 ^ 10来解决是无效的.

如何优化这个..

编辑: 解决方案:对每个j使用Primality测试.

米勒拉宾,费马的测试.

所以我一直在尝试通过解决 Codeforce 上的一些问题来学习 Haskell。
即使我认为我的时间复杂度是最佳的，我也得到了很多 TLE（超出时间限制）。

我的问题是：是我编写这个程序的方式使它变慢了吗？

例如，这里是问题。

基本上答案是找到给定的，其中 and =和之间的除数数之差。annan = 2*an-1 + D(n)D(n)nn-1

（更新：上限为n10 ⁶）。

下面是我的程序。

import qualified Data.Map.Strict as Map

main = do t <- read <$> getLine
          putStrLn . show $ solve t

solve :: Integer -> Integer
solve 0 = 1
solve 1 = 1
solve n = (2*(solve (n-1)) + (fact n) - (fact (n-1))) `mod` 998244353
    where fact …

这是我的代码,它只能输出素数.

#include <stdio.h>
int prime(int n){
    int j;
    for (j=2;j<=n/2;j++){
        if((n%j)==0){
            return 0;
        }
        else{
            return 1;
        }
    }
}
void main(){
    int i,p;
    for (i=2;i<=100;i++){
        p=prime(i);
        if(p==1){
            printf("%d \n",i);
        }
    }
}

结果是2,3,7,9,11,13,15 ....

不是2,3,5,7,11,13 ....

我做错了什么？

所以重点是让程序找到并列出1和你输入的数字之间的所有素数.我使用number_test作为测试素数,除数和除数的数字.

我不确定是什么问题,对我来说,它看起来在功能上与此处发布的程序相同:从1到100打印素数 并进行一些小的更改(输入数字,将"i"更改为小于输入的数字).

我一直在寻找过去的三四天,而且我没有找到任何能够完全回答这个问题的东西,达到我课堂上所需要的程度.任何帮助深表感谢.

#include iostream
#include conio.h
using namespace std;

void main(void){
//Declare variables
int number_entered;
//Get inputs    
cout << "This program lists all prime numbers from 1 through a positive number entered."
 << endl;
cout << "Please enter a positive integer."
 << endl;
cin >> number_entered;
cout << "Displaying all numbers from 1 to " << number_entered
 << endl
 << "Press any key to continue..."
 << endl;
getch();

for(int number_test = 2; number_test < number_entered; number_test++){
    for(int …

好的,我想从控制台输入一个整数,并检查数字是否为素数.我挖出了一个代码,然后根据我的需要对其进行了转换,但计算不正确.

using System;
    class PrimeNumber
    {
    static void Main()
    {
        Console.Write("Type a number: ");
        string line = Console.ReadLine(); // Read string from console
        int value;
        if (int.TryParse(line, out value)) // Try to parse the string as an integer
        {
            int x = 0;
            if (value == 1) Console.WriteLine("not prime");
            if (value == 2) Console.WriteLine("prime");
            for (int i = 3; i < value*value; i+=2)
            {
                if (value % 2 == 0) x++; break;
                if (value % i == 0) x++; break; …

我正在尝试使用C#查找数字是否为素数.我写了代码.它应该工作,但由于某种原因它似乎没有.

这是我的代码(我尝试输入7,13等,说它们不是素数):

class Program
{
    static void Main(string[] args)
    {
        long u = Console.Read();
        primefinder(u);
        Console.ReadLine();
    }

    private static void primefinder(long a)
    {
        long counter = 0;
        for (long b = 1; b <= a; b++)
        {
            if ((a % b) == 0)
            {
                counter++;
            }
        }

        if (counter == 2)
        {
            Console.WriteLine("Is prime!");
        }

        else
        {
            Console.WriteLine("Is not prime");
        }

        Console.ReadLine();
    }
}

我必须确定列表中的所有数字是否都是素数，然后根据结果返回布尔“True”或“False”语句。我在 for 循环中做了一些条件语句来查看该数字是否为素数。

这是代码：

def all_primes(xs):
    is_prime = None
    for i in xs:
        if i < 2:
            is_prime = False
            return is_prime
            break
        elif (i % 2 == 0) and (i % i == 1):
            is_prime = False
            return is_prime
            break
        else:
            is_prime = True
            return is_prime

问题是，我在 Python Visualizer 中看到了这一点，for 循环在检查列表中的第一个值后停止迭代。我不明白为什么，因为语法与我过去使用的 for 循环相同。

我插入了一些示例值，例如：all_primes([5,2,11,37])or all_primes([5,2,4,37])，并且返回值始终为 true，因为 5 是列表中的第一个数字，也是唯一被迭代的数字。

有什么想法吗？

这个问题是检查数字是否为素数,当然已经有不同的答案了.但是我整天都在努力,我找不到为什么我的方法不能正常工作.

public class PrimeNum 
{
    private static boolean isPrime;
    private static Scanner input;

    public static void main(String[] args)
    {
        input = new Scanner(System.in);
        System.out.println("Enter a prime number ( you think ) : ");
        int num = input.nextInt();

        isPrime = false;
        for(int divisor = 2; divisor < num / 2; divisor++) {
            if(num % divisor == 0)
            {

                isPrime = false;
            }
            isPrime = true;
        }
        if(isPrime)
        {
            System.out.println("Prime");

        }
        else
        {
            System.out.println("Not a prime");
        }
    }
}

我一直在寻找解决方案来质疑10001的素数是多少.我完成了代码:

int main() {
    long long listNumber[10001];
    long position = 1, divider = 0;

    listNumber[0] = 2;

    while(listNumber[10000] == 0) {
        divider = 0;
        listNumber[position] = listNumber[position-1] + 1;

        while(listNumber[divider] <= sqrt(listNumber[position])) {
            if(listNumber[position] % listNumber[divider] == 0) {
                listNumber[position]++;
                divider = 0;
            } else divider++;
        }

        position++;
    }

    cout << listNumber[10000] << endl;

    return 0;
}

但输出总是在变化,我不知道为什么.你能帮我解决一下吗？谢谢.

我需要编写一个从用户那里接收一个数字(n)的函数,该函数返回一个包含所有素数的数组,直到用户编号(n).我知道如何编写检查数字是否为素数的函数,但我不知道如何将数字输入数组...例如,如果用户输入53,它将返回[2,3,5,7,11, 13,17,19,23,29,31,37,41,43,47,53].我忘了告诉那语言是java ..我的坏!

尝试存储质数并输出它们，但控制台是空的，什么也没有发生

int main() {
    vector <int> v;
    int n = 1000;
    
    int order; // Nth order
    //cin >> order;
    primes(n, v);
    for (auto i = v.begin(); i != v.end(); ++i)
        cout << *i << ' ';
    return 0;
}

分析版本的复图

在所有 Covid 停机期间，我一直在做一些数论，我想我发现了一种非常有趣（如果不是新颖的）检测素性的算法。我在我的 LinkedIn 页面上发布了我的文章，您无需注册或进行任何操作。

https://www.linkedin.com/pulse/efficient-prime-number-generation-christopher-wolfe/

我只想知道这种技术是否已经为人所知，因为它非常快（恒定时间）并且尺寸非常紧凑。不久前我进行了更深入的研究，您可以在我的博客上阅读。

http://jasuto.com/ideas/primes/

获得一些反馈并验证这是新的会很棒。我还有很多要发布，但我想我会开始轻松:)

如果您不想阅读本文，这里是演示代码。我见过很多质数实现，但没有 O(1) 或这么小的......

# Copyright 2021 Christopher Wolfe (chris@jasuto.com)
# Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do …

以下代码用于质数。我想知道为什么我们i<=n/2在循环中使用条件。

C程序：

#include <stdio.h>
int main()
{
int n, i, flag = 0;

printf("Enter a positive integer: ");
scanf("%d",&n);

for(i=2; i<=n/2; ++i)
{
    // condition for nonprime number
    if(n%i==0)
    {
        flag=1;
        break;
    }
}

if (flag==0)
    printf("%d is a prime number.",n);
else
    printf("%d is not a prime number.",n);

return 0;
}