c - 计算Haskell的倍数(从C转换)？

Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗？更新问题，使其只关注一个问题editing this post。
去年关门了。
我想写一个计算倍数的Haskell程序。基本上，当给定两个整数a和b时，我想知道1≤b I≤b是2≤ai≤a的任意整数的倍数。例如，如果a=3和b=30，我想知道1-30范围内有多少整数是2或3的倍数；有20个这样的整数：2、3、4、6、8、9、10、12、14、15、16、18、20、21、22、24、26、27、28，三十
我有一个C程序来做这个。我正试图将此转换为Haskell，但部分困难在于绕过Haskell不使用循环以来我使用的循环。我非常感谢大家的帮助！
我的C程序供参考（如果格式设置已关闭，则很抱歉）：

#define PRIME_RANGE 130
#define PRIME_CNT   32

#define UPPER_LIMIT (1000000000000000ull) //10^15
#define MAX_BASE_MULTIPLES_COUNT  25000000

typedef struct
{
    char primeFactorFlag;
    long long multiple;
}multipleInfo;

unsigned char primeFlag[PRIME_RANGE + 1];
int primes[PRIME_CNT];
int primeCnt = 0;

int maxPrimeStart[PRIME_CNT];
multipleInfo baseMultiples[MAX_BASE_MULTIPLES_COUNT];
multipleInfo mergedMultiples[MAX_BASE_MULTIPLES_COUNT];
int baseMultiplesCount, mergedMultiplesCount;

void findOddMultiples(int a, long long b, long long *count);
void generateBaseMultiples(void);
void mergeLists(multipleInfo listSource[], int countS, multipleInfo

listDest[], int *countD);
void sieve(void);

int main(void)
{

    int i, j, a, n, startInd, endInd;
    long long b, multiples;

    //Generate primes
    sieve();
    primes[primeCnt] = PRIME_RANGE + 1;

    generateBaseMultiples();
    baseMultiples[baseMultiplesCount].multiple = UPPER_LIMIT + 1;

    //Input and Output
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
    {
        scanf("%d%lld", &a, &b);

        //If b <= a, all are multiple except 1
        if(b <= a)
            printf("%lld\n",b-1);
        else
        {
            //Add all even multiples
            multiples = b / 2;
            //Add all odd multiples
            findOddMultiples(a, b, &multiples);-

            printf("%lld\n", multiples);
        }
    }
    return 0;
}

void findOddMultiples(int a, long long b, long long *count)
{
    int i, k;
    long long currentNum;

    for(k = 1; k < primeCnt && primes[k] <= a; k++)
    {
        for(i = maxPrimeStart[k]; i < maxPrimeStart[k + 1] &&

baseMultiples[i].multiple <= b; i++)
        {
            currentNum = b/baseMultiples[i].multiple;
            currentNum = (currentNum  + 1) >> 1; // remove even multiples
            if(baseMultiples[i].primeFactorFlag) //odd number of factors
                (*count) += currentNum;
            else
                (*count) -= currentNum;
        }
    }
}

void addTheMultiple(long long value, int primeFactorFlag)
{
    baseMultiples[baseMultiplesCount].multiple = value;
    baseMultiples[baseMultiplesCount].primeFactorFlag = primeFactorFlag;
    baseMultiplesCount++;
}

void generateBaseMultiples(void)
{
    int i, j, t, prevCount;
    long long curValue;

    addTheMultiple(3, 1);
     mergedMultiples[0] = baseMultiples[0];
    mergedMultiplesCount = 1;

    maxPrimeStart[1] = 0;
    prevCount = mergedMultiplesCount;
    for(i = 2; i < primeCnt; i++)
    {
        maxPrimeStart[i] = baseMultiplesCount;
        addTheMultiple(primes[i], 1);
        for(j = 0; j < prevCount; j++)
        {
            curValue = mergedMultiples[j].multiple * primes[i];
            if(curValue > UPPER_LIMIT)
                break;

            addTheMultiple(curValue, 1 - mergedMultiples[j].primeFactorFlag);
        }
        if(i < primeCnt - 1)
            mergeLists(&baseMultiples[prevCount], baseMultiplesCount - prevCount, mergedMultiples, &mergedMultiplesCount);

        prevCount = mergedMultiplesCount;
    }
    maxPrimeStart[primeCnt] = baseMultiplesCount;
}

void mergeLists(multipleInfo listSource[], int countS, multipleInfo listDest[], int *countD)
{
int limit = countS + *countD;
int i1, i2, j, k;

//Copy one list in unused safe memory
for(j = limit - 1, k = *countD - 1; k >= 0; j--, k--)
    listDest[j] = listDest[k];

//Merge the lists
for(i1 = 0, i2 = countS, k = 0; i1 < countS && i2 < limit; k++)
{

    if(listSource[i1].multiple <= listDest[i2].multiple)
        listDest[k] = listSource[i1++];
    else
        listDest[k] = listDest[i2++];
}

while(i1 < countS)
    listDest[k++] = listSource[i1++];


while(i2 < limit)
    listDest[k++] = listDest[i2++];

*countD = k;
}

void sieve(void)
{
   int i, j, root = sqrt(PRIME_RANGE);
    primes[primeCnt++] = 2;
    for(i = 3; i <= PRIME_RANGE; i+= 2)
    {
        if(!primeFlag[i])
        {
            primes[primeCnt++] = i;
            if(root >= i)
            {
                for(j = i * i; j <= PRIME_RANGE; j += i << 1)
                primeFlag[j] = 1;
        }
    }
}
}

最佳答案

首先，除非我有严重的误解，否则你的倍数是错误的。1到30之间2的倍数是15，1到30之间3的倍数是10，所以应该有25个数字。
编辑：我误解了，你想要独特的倍数。
要得到唯一的倍数，可以使用Data.Set，它具有集合元素唯一且按升序排列的不变量。
如果您知道您不会超过x = maxBound :: Int，则可以使用Data.IntSet获得更好的加速。我还包括了一些测试用例，并用注释注释了它们在我的机器上运行的目的。

{-# LANGUAGE BangPatterns #-}

{-# OPTIONS_GHC -O2 #-}

module Main (main) where

import System.CPUTime (getCPUTime)
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet

main :: IO ()
main = do
  test 3 30       -- 0.12 ms
  test 131 132    -- 0.14 ms
  test 500 300000 -- 117.63 ms

test :: Int -> Int -> IO ()
test !a !b = do
  start <- getCPUTime
  print (numMultiples a b)
  end   <- getCPUTime
  print $ "Needed " ++ show ((fromIntegral (end - start)) / 10^9) ++ " ms.\n"

numMultiples :: Int -> Int -> Int
numMultiples !a !b = IntSet.size (foldMap go [2..a])
  where
    go :: Int -> IntSet
    go !x = IntSet.fromAscList [x, x+x .. b]

关于c - 计算Haskell的倍数(从C转换)？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49785721/