C语言判断质数,for语句里一个条件看不懂?

Python014

C语言判断质数,for语句里一个条件看不懂?,第1张

看到提问者,迟迟没有采纳别人的答案,我就来答一下,因为其他人虽然说了,但是楼主可能没有明白是为什么。。。我专门详细的给你讲解一下吧。。。

首先,直接写i<n,是可以的,但是效率太低。假设,我输入的数n是100,那么显而易见,for循环需要做一百次,貌似没差哦,因为电脑的运行速度是很快的,可能几秒钟就做完100次for循环了。但是要是我输入的100000,十万呢?那么意味着,需要做10万次for循环,这个时候,计算机可能需要几十秒,感觉还是很快是吧,不差那几十秒对吧,那我们如果输入更大的数,10亿呢?可能就需要一分钟了,因为计算机虽然算的快,但是不意味着瞬间就能完成啊。所以那怎么办呢?我们需要对程序进行优化,即采用算法,从而提高效率和运行速度,这就是计算机专业的基本课程要求了,我就不细讲了。主要讲一下,这个程序,为什么要这么做。

首先,我知道,我们需要提高for循环的效率,从而尽可能的让for循环的次数少,从而减少时间,提高运行效率,那么我们应该怎么提高呢。假设,我们现在还输入数n为100,i<n,需要100次,那么我需要减少运行次数,所以我们需要先分析一下,怎么减少,比如i<n,当n=100的时候,我们需要100次,提高效率,那么我就要把上限n减小。当我输入n=100,是先从i=2开始做的对吧,这个时候100/2,结果是50对吧,那么请问50以上的数我还需要做吗?没必要对吧,因为100/60,结果已经小于2了,而我们的i是从2开始一直往上加的正整数,50以上的数明显小于2,做第一遍的时候,不符合,那么50上面的数一定不符合了啊对吧,这个时候,我们就可以写for(i=2i<n/2i++),这样效率就提高一半了,原来要从2做到100,现在只要做到50,而且我们也已经知道了,为什么50以上的数不需要做了,效率提高了将近一半,但是效率依然可以继续提高,就像你那个程序一样,那么当i=3的时候呢?100/3=33.33,取整就是33,就算向上取整,也才34,那么意味着,如果这个数能被3整除,那么34-100的数就不需要去做了,因为如果能被3整数,那么33以上的数肯定有一个能被整除,而3都不能整除的话,那么34以上的数一定找不到能被整除的数了,所以我们会发现i每次增加1了之后,我们要寻找的数的上线就被降低了,根本不需要做到这个数为止,那么极限数是什么呢?很简单,当i增大了,我们的上线就减少了,最后的上限的极限在哪里呢?上限的极限就在100/i=i,为啥呢?因为i的平方数等于100,也就是意味着i*i=100,如果能被整除,那么i就是唯一的整除的数,如果i不是,那么就一定没有,因为i如果继续增加,那么另外一个能被整除的数一定小于i,但是小于i的正整数,我们已经全部做过了啊。所以当i*i=100,都没有结果的时候,根本不需要再往上做了,如果在小于i的范围内,有一个数能被整除,那么这个数是质数还是素数,我们就已经很清楚了吧,就不需要再去做了,除非你的程序,是要把所有能被整除的数都找出来。

所以,其实那只是一个算法而已,目的,只是在于提高效率。而i<n可以,但是效率略低,而且当输入的数越大,效率越低,找出答案的时间越长,不信你可以输入一个超级大的数,黑框的控制台,就不会马上出结果,超级大的数,你甚至还会以为程序卡主了,其实是程序没做完而已。。。没巴拉算法之前,我写程序也是暴力群举的,简单小程序,确实够用了,大程序,是行不通的,一定是需要算法辅助的。。。

我说了这么多,应该已经比他们详细明了了吧,自己去算算,就知道了,要尽可能的把上限缩小,如果只是初学者,不用关心这个,先把C语言的程序语法,标准语句搞清楚,会用,没有BUG就行了。。。

int i,n=strlen(a)

for(i=0i<ni++)

if(a[i]>='a'&&a[i]<='z')

a[i]-=32

else if(a[i]>='A'&&a[i]<='Z')

a[i]+=32

return a[n]