标签: prime-factoring

我试图找到大数量产品的因素.

问题陈述是这样的:假设给你N个数字(假设N = 10),每个数字<= 1000000.如何找到这些数字乘积的因子数.

有人可以提供一个有效的算法来做到这一点.

示例:

1)N = 3,数字为3,5,7

Ans = 8(1,3,5,7,15,21,35,105)

2)N = 2且数字为5,5

Ans = 3(1,5和25)

我试图解决Haskell中的Euler问题3,它涉及找到数字的最大素数因子.我的代码运行了很长时间,似乎挂了.是什么导致我的代码如此低效？

primes = sieve (2:[3,5..])
 where sieve (x:xs) = x:[y | y <- (sieve xs), mod y x /= 0]
       sieve [] = []
primefactors n = filter (\x -> mod n x == 0) (primesUnder n)
 where primesUnder z = reverse (takeWhile (< z) primes)
solve3 = head (primefactors 600851475143)

我试图打印出一个数字的所有主要因素.我的代码如下:

public static boolean isPrime(long n){

    long i = n;

    while (i > 0){

        if (n % i == 0 && !(i == 1 || i == n)){

            return false;

        }
        i--;
    }

    return true;

}


public static void primeFactors(long n){

    long i = n;
    while (i > 0){

        if (isPrime(i)){
            System.out.println(i);
        }
        i--;
    }

}

此代码适用于小数字:5,5000,例如,当我向方法输入600851475143时,我的程序运行,没有输出任何内容.为什么会这样？

我想知道是否有可能通过在C#中使用模数来找到数字的最大素数因子.换句话说,如果i % x == 0那时我们可以打破一个for循环或类似的东西,其中x等于低于我们的i值的所有自然数.

我如何指定all natural numbers below our i value等于我们的x变量？如果你知道我在说什么,写出每个整数的条件变得有点乏味.

顺便说一句,我敢肯定有一个远更简单的方法在C#中要做到这一点,所以请让我知道,如果你有一个想法,但我也想尝试解决这种方式,只是为了看看如果我能用我的初学者知识做到这一点.

这是我目前的代码,如果你想看到我到目前为止:

static void Main()
{
    int largestPrimeFactor = 0;

    for (long i = 98739853; i <= 98739853; i--)
    {
        if (true)
        {
            largestPrimeFactor += (int) i;
            break;
        }
    }

    Console.WriteLine(largestPrimeFactor);
    Console.ReadLine();
}

我一直在尝试在Scala中解决3中的项目Euler数,这是我到目前为止所得到的:

def largestPrimeFactor(in:BigInt) : Option[BigInt] = {
  def isPrime(in:BigInt) : Boolean = {
    def innerIsPrime(in:BigInt, currentFactor:BigInt) : Boolean = {
        if(in % currentFactor == 0) {
        false
      }
      else {
        if(currentFactor > (in / 2)){
           true
        }
        else {
          innerIsPrime(in, currentFactor + 1)
        }
      }
    }

     innerIsPrime(in, 2)
  }

   def nextLargeFactor(in:BigInt, divisor:BigInt) : (Option[BigInt], BigInt) = {
     if((in / 2) > divisor) {
       if(in % divisor == 0) (Some(in / divisor), divisor) 
       else nextLargeFactor(in, divisor + …

我正在做一个java家庭作业,其中一部分就是编写一个程序来查找素数.我知道有一条规则,数字的平方根将有助于确定给定的数字是否为素数.我不完全理解这个概念.取37是素数.如果我取37的平方根,则为6.0827.所以我理解的规则是,我不需要对任何大于平方根的数进行测试和除以37,即向下舍入为6.

我的问题是,如果你在6点停止,你怎么知道你的给定数字不能被8整除？在素数与平方根之间的关系中,我的理解是正确的,还是我错过了什么？

37%2 =(2*18 = 36)余数1

37%3 =(3*12 = 36)余数1

37%4 =(9*4 = 36)余数1

37%5 =(7*5 = 35)余数2

37%6 =(6*6 = 36)余数1

规则说停止在这一点上.------------

37%7 =(7*5 = 35)余数2

37%8 =(8*4 = 32)余数5

37%9 =(9*4 = 36)余数1

import java.lang.*;
import java.math.*;

class Factor
{
    public void Factor(double NumToFactor)
    {
        for (double i=0; i <= Math.sqrt(NumToFactor); i++)
        {
            if (NumToFactor%i == 0)
            {
                Factor(NumToFactor/i);
                System.out.println(i + "*");
            }
        }
    }

}

public class PrimeFactorization 
{

    public static void main(String[] args) 
    {
        System.out.println(Factor(120.0)); 
    }
}

我收到以下错误（我很困惑）：

错误：找不到符号 (double i=0; i <= Math.sqrt(NumToFactor); i++)

所以我遇到了一个我似乎无法解决的问题。我想显示因子和它被提升到的功率（基本上是质因子分解），我已经在 python 中完成了这个，但由于某种原因我不能在 C 中实现它，这就是我想出的

#include<stdio.h>
#include<math.h>

int main()
{
    int i = 2, p, c, n;
    scanf("%d", n);
    while (n > 9)
    {
        p = 0;
        c = 1;
        while (n % i == 0)
        {
            for (int d = 2; d <= i / 2 + 1; d++)
                if (i % d == 0 && i % 2 != 0)
                    c = 0;
            if (c == 1)
            {
                p = p + 1;
                n = n / i; …

你有一个自然数m。

您需要编写一个函数 f(m) 来查找满足 n^n\xe2\x89\xa10 mod m 的最小正数 n。

换句话说，n^n 可以被 m 整除。

例如：

f(13) = 13\nf(420) = 210\nf(666) = 222\nf(1234567890) = 411522630\n

这是我的 python 代码。

import math\n\ndef f(m: int) -> int:\n    t = math.isqrt(m) + 1\n    primes = [1 for i in range(0, t)]\n\n    maxCount = 0\n    factors = []\n    p = 2\n\n    result = 1\n\n    while p < t and p < m:\n        if primes[p] == 1 and m % p == …

如何使用下面的IsPrime方法测试质数？我似乎无法让printf在我的IsPrime方法中工作,并且没有抛出任何错误.

#include <stdlib.h>
#include <stdio.h>
int IsPrime(unsigned int number) {
   if (number <= 1) {
      return 0; // zero and one are not prime
      printf("zero and one are not prime.");
      }
   unsigned int i;
   for (i=2; i*i<=number; i++) {
      if (number % i == 0) {
         return 0;
         printf("not a prime.");
      }
   }
   return 1;
   printf("You've found a prime!");
   }

int main(void) {
   int a;

   printf("Please input an integer value: ");
   scanf("%d", &a);
   if(a >= 1 && a <= 1000) …