C程序: Does not execute beyond 1000 or just hangs

Question

这个程序是找到三个四位质数，它们是彼此的排列，并且它们之间的差为 3320。现在，以下程序可以正确生成素数，但执行会在值 1000 之后停止或挂起。为什么会发生这种情况以及如何纠正它？

#include<stdlib.h>
#include<stdio.h>
#define LIMIT 1000000
long int arr[LIMIT];
int Bsearch(long int *primes,long int low,long int high,long int search)
{
    while(low<=high)
    {   
        long int mid=(low+high)/2;

        if(search<primes[mid])
        {
            high=mid+1;
        }
        else if(search>primes[mid])
        {
            low=mid+1;
        }
        else if(search==primes[mid])
            return 1;
    }
    return 0;
}

int checkPermu(long int *primes,long int i,long int j,long int k)
{
    long int prod1=1;
    long int prod2=1;
    long int prod3=1;
    for(int i=0;i<3;i++)
    {
        prod1*=primes[i%10];prod2*=primes[j%10];prod3*=primes[k%10];
        i/=10;j/=10;k/=10;
    }
    prod1*=primes[i];prod2*=primes[j];prod3*=primes[k];
    if(prod1==prod2==prod3)
        return 1;
    else 
        return 0;
}

int main()
{
    for(long int i=1;i<LIMIT;i++)
    {
        arr[i]=1;
    }

    for(long int i=2;i<LIMIT;i++)
    {
        if(arr[i]==1)
        {
            for(long int j=2;i*j<LIMIT;j++)
            {
                arr[i*j]=0;
            }
        }
    }
    long int index=0;
    long int count=0;
    //count number of primes
    for(long int i=1;i<LIMIT;i++)
    {
        if(arr[i]==1) count++;
    }
    long int primes[count];
    for(long int i=2,index=1;i<LIMIT;i++)
    {
        if(arr[i]==1)
            primes[index++]=i;
    }

    for(long int i=1000;i<9999;i++)
    {
        printf("\nCurrent num : %ld\n",i);
        if(Bsearch(primes,1,count-1,i))
        {
            printf("Hello1!");
            if(Bsearch(primes,1,count-1,i+3330))
            {
                printf("\nHello2!");
                if(Bsearch(primes,1,count-1,i+3330+3330))
                {
                    printf("\nHello3!");
                    if(checkPermu(primes,i,i+3330,i+3330+3330))
                    {
                        printf("\nFinal Hello!");
                        printf("required sequence : %ld%ld%ld",i,i+3330,i+3330+3330);
                        exit(0);
                    }
                }
            }
        }
    }
    return 0;
}

Answer 1

您的代码中有很多错误。

• 在函数Bsearch中，您正在数组中搜索一个值。如果它不存在怎么办？就您而言，1000 不是素数。所以，你在数组中找不到它。仅当该值完全匹配时，您才会退出循环。在这种情况下不会发生这种情况，最终会陷入无限循环

• 在函数 checkPermu 中，有两个变量声明为 i。这意味着您正在隐藏作为参数传递的 i 。为了避免这种情况，请给它起一个其他名称。

现在，为了避免第一种情况，您可以使用 C++ 中的内置函数，lower_bound ，或者相应修改代码。这是您编辑的代码。

#include <stdlib.h>
#include <stdio.h>

#define LIMIT 1000000

long int arr[LIMIT];

int Binary_Search(long int a[], int low, int high, long int e)
{
    if ( low < 0) return 0;
    if (low>=high )
    {
      if ( e <= a[low] ) return low;
      return low+1;
    }
    int mid=(low+high)/2;
    if ( e> a[mid])
        return Binary_Search(a,mid+1,high,e);
    return Binary_Search(a,low,mid,e);

}
int Bsearch(long int *primes,long int low,long int high,long int search)
{
    int idx = Binary_Search(primes, low, high+1,search);
    if(primes[idx]==search)
        return 1;
    return 0;
}
int checkPermu(long int *primes,long int ii,long int j,long int k)
{
    long int prod1=1;
    long int prod2=1;
    long int prod3=1;

    for(int i=0;i<3;i++)
    {
        prod1*=primes[ii%10];prod2*=primes[j%10];prod3*=primes[k%10];
        ii/=10;j/=10;k/=10;

    }
    prod1*=primes[ii];prod2*=primes[j];prod3*=primes[k];
    if(prod1==prod2==prod3)
        return 1;
    else 
        return 0;
}

int main()
{
    for(long int i=1;i<LIMIT;i++)
    {
        arr[i]=1;
    }

    for(long int i=2;i<LIMIT;i++)
    {
        if(arr[i]==1)
        {
            for(long int j=2;i*j<LIMIT;j++)
            {
                arr[i*j]=0;
            }
        }
    }
    long int index=0;
    long int count=0;
    //count number of primes
    for(long int i=1;i<LIMIT;i++)
    {
        if(arr[i]==1) count++;
    }
    long int primes[count];
    for(long int i=2,index=1;i<LIMIT;i++)
    {
        if(arr[i]==1)
            primes[index++]=i;
    }
    //Bsearch(primes,1,count-1,1000);
    for(long int i=1000;i<9999;i++)
    {
        printf("\nCurrent num : %ld\n",i);
        if(Bsearch(primes,1,count-1,i))
        {
            printf("Hello1!\n");
            if(Bsearch(primes,1,count-1,i+3330))
            {
                printf("\nHello2!\n");
                if(Bsearch(primes,1,count-1,i+3330+3330))
                {
                    printf("\nHello3!\n");
                    if(checkPermu(primes,i,i+3330,i+3330+3330))
                    {
                        printf("\nFinal Hello!\n");
                        printf("required sequence : %ld%ld%ld",i,i+3330,i+3330+3330);
                        exit(0);
                    }
                }
            }
        }
    }
    return 0;
}