标签: primes

我写了下面的代码,应该检查输入的数字是否是素数,但是有一个问题我无法通过:

def main():
n = input("Please enter a number:")
is_prime(n)

def is_prime(a):
    x = True 
    for i in (2, a):
            while x:
               if a%i == 0:
                   x = False
               else:
                   x = True


    if x:
        print "prime"
    else:
        print "not prime"

main()

如果输入的数字不是素数,则显示"非素数",因为它应该是,但如果数字是素数,则它不显示任何内容.你能帮帮我吗？

我一直在努力解决Clojure中的Project Euler问题,以便变得更好,而且我已经遇到了几次素数.我的问题是它只是花了太长时间.我希望有人可以帮我找到一种以Clojure-y方式做到这一点的有效方法.

当我拳头做到这一点时,我粗暴地强迫它.这很容易做到.但是计算10001个素数在Xeon 2.33GHz上用了2分钟,对规则来说太长了,一般来说太长了.这是算法:

(defn next-prime-slow
    "Find the next prime number, checking against our already existing list"
    ([sofar guess]
        (if (not-any? #(zero? (mod guess %)) sofar)
            guess                         ; Then we have a prime
            (recur sofar (+ guess 2)))))  ; Try again                               

(defn find-primes-slow
    "Finds prime numbers, slowly"
    ([]
        (find-primes-slow 10001 [2 3]))   ; How many we need, initial prime seeds
    ([needed sofar]
        (if (<= needed (count sofar))
            sofar                         ; Found enough, we're done
            (recur needed (concat sofar [(next-prime-slow …

两部分问题......

1)试图确定600851475143的最大素数因子,发现这个程序似乎在线工作,问题是我很难弄清楚它是如何工作的(我理解程序正在做什么的基础)...另外,如果您能够了解一些您可能知道找到素数的方法(可能没有测试每个数字)以及您的方法是如何工作的.

我在网上找到的主要因素代码

n = 600851475143
i = 2
while i * i < n:
     while n % i == 0:
         n = n / i
     i = i + 1

print (n)

#takes about ~0.01secs

2)为什么代码比这段代码快得多(代码只是测试速度而没有其他真正的用途)

i = 1
while i < 100:
    i += 1
#takes about ~3secs

谁能告诉我为什么在DJB哈希函数中使用数字5381？

DJB Hash功能是

h(0)= 5381

h(i)= 33*h(i-1)^ str [i]

一个c程序:

unsigned int DJBHash(char* str, unsigned int len)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {   
      hash = ((hash << 5) + hash) + (*str);
   }   

   return hash;
}

所以我能够通过互联网的一些帮助来解决这个问题,这就是我得到的:

def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False

    return True

但我的问题是如何做到这一点,但为什么.我知道1不被认为是"素数",即使它是,并且我理解如果它在范围内除以ANYTHING则自动为素数,因此返回False语句.但我的问题是"n"在这里的平方是什么角色？非常感谢您的关注

Ps我非常缺乏经验,一个月前刚刚开始编程:S

我错误地认为RSA加密的安全性通常受已知素数的限制吗？

要破解(或创建)私钥,必须组合正确的素数对.

是否无法发布RSA使用范围内所有素数的列表？或者这个列表足够大,以使这种暴力攻击不太可能？难道不会有"常用"素数吗？

只有素数因子为2,3或5的数字称为丑陋数字.

例:

1,2,3,4,5,6,8,9,10,12,15 ......

1可以被认为是2 ^ 0.

我正在努力寻找第n个难看的数字.请注意,当n变大时,这些数字非常稀疏地分布.

我写了一个简单的程序来计算给定数字是否丑陋.对于n> 500 - 它变得超级慢.我尝试使用memoization - 观察:ugly_number*2,ugly_number*3,ugly_number*5都很难看.即便如此,它也很慢.我尝试使用log的一些属性 - 因为这会将这个问题从乘法减少到另外 - 但是,运气不大.想与大家分享这个.任何有趣的想法？

使用类似于"Eratosthenes的筛子"的概念(感谢Anon)

    for (int i(2), uglyCount(0); ; i++) {
            if (i % 2 == 0)
                    continue;
            if (i % 3 == 0)
                    continue;
            if (i % 5 == 0)
                    continue;
            uglyCount++;
            if (uglyCount == n - 1)
                    break;
    }

我是第n个难看的数字.

即便这样也很慢.我想找到第1500个难看的数字.

我想问一下这是否是检查数字是否为素数的正确方法？因为我读到0和1不是素数.

int num1;

Console.WriteLine("Accept number:");
num1 = Convert.ToInt32(Console.ReadLine());
if (num1 == 0 || num1 == 1)
{
    Console.WriteLine(num1 + " is not prime number");
    Console.ReadLine();
}
else
{
    for (int a = 2; a <= num1 / 2; a++)
    {
        if (num1 % a == 0)
        {
            Console.WriteLine(num1 + " is not prime number");
            return;
        }

    }
    Console.WriteLine(num1 + " is a prime number");
    Console.ReadLine();
}

我使用Sieve of Eratosthenes和Python 3.1 编写了一个素数生成器.代码在ideone.com上以0.32秒正确且优雅地运行,以生成高达1,000,000的素数.

# from bitstring import BitString

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...    
    using Sieve of Eratosthenes.
    '''
    yield 2
    sub_limit = int(limit**0.5) 
    flags = [False, False] + [True] * (limit - 2)   
#     flags = BitString(limit)
    # Step through all the odd numbers
    for i in range(3, limit, 2):       
        if flags[i] is False:
#        if flags[i] is True:
            continue …

我正在尝试计算素数,我已经完成了.但我想计算并打印第n个素数(用户输入),在计算其余部分(它们不会被打印)时,只打印第n个素数.

这是我到目前为止所写的内容:

import java.util.Scanner;
/**
 * Calculates the nth prime number
 * @author {Zyst}
 */
public class Prime {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int n, 
            i = 2, 
            x = 2;

        System.out.printf("This program calculates the nth Prime number\n");
        System.out.printf("Please enter the nth prime number you want to find: ");
        n = input.nextInt();

        for(i = 2, x = 2; i <= n; i++) {
            for(x = 2; x < i; x++) {
                if(i % …