A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 张小康 于 2013-11-4 20:26 编辑

用方法来实现:计算1-100之间的所有质数(素数)的和。

评分

参与人数 1技术分 +1 收起 理由
追溯客 + 1

查看全部评分

11 个回复

倒序浏览
        static void Main(string[] args)
        {

            //用方法来实现:计算1-100之间的所有质数(素数)的和。
            int sum = GetPrimeSum();
            Console.WriteLine(sum);
            Console.ReadKey();
        }
         /// <summary>
        /// 判断一个整数是不是质数
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static bool IsPrime(int n)
        {
            bool b = true;
            if (n < 2)
            {
                b = false;
            }
            else
            {

                for (int i = 2; i <= n - 1; i++)
                {
                    if (n % i == 0)
                    {
                        b = false;
                        break;
                    }
                }
            }
            return b;
        }
        public static int GetZhiSum()
        {
            int sum = 0;
            for (int i = 1; i <= 100; i++)
            {
                if (IsPrime(i))
                {
                    sum += i;

                }
            }
            return sum;
        }

评分

参与人数 1技术分 +1 收起 理由
陈福军 + 1

查看全部评分

回复 使用道具 举报
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 素数的和
{
    class Program
    {
        static void Main(string[] args)
        {
            int sum=0;//总和
            for (int i = 0; i < 100; i++)
            {
                if (IsPrime(i))
                {
                    sum += i;
                }
            }
            Console.WriteLine(sum);
        }
        public static bool IsPrime(int number)//判断一个数是否是质数
        {
            if (number < 2)//小于2 不是素数
            {
                return false;
            }
            else if (number == 2)//等于2是素数
            {
                return true;
            }
            else
            {
                for (int i = 2; i < number; i++)//大于2 进行判断
                {
                    if (number % i == 0)
                    {
                        return false;
                    }
                }
                return true;
            }
        }
    }
}

评分

参与人数 1技术分 +1 收起 理由
陈福军 + 1

查看全部评分

回复 使用道具 举报
楼上两位已经把代码贴出来了,  处理这个100内的素数之和是没问题的。
不过如果想优化一下的话, 还是有一个点可以优化的。
在判断某一个数是否为素数的时候, 楼上两位都判断到n-1了(n为需要判断的数字), 实际上只需要判断到n/2 - 1就可以了。

评分

参与人数 1技术分 +1 收起 理由
陈福军 + 1

查看全部评分

回复 使用道具 举报
本帖最后由 大虾挂了 于 2013-11-3 05:11 编辑

求1-100内所有素数的和么?我认为这里最快的方法涉及到2个问题,一个i是判断因子的时候,究竟要判断哪些数字,另一个是究竟判断到什么位置就OK。

1、合数必然能分解成一些素数的乘积,这是其一,所以判断因子的时候只需判断素数即可。没必要2、3、4、5、6。。。。。。连续判断
如果这里不理解,举几个例子,比如判断完2不是num的因子,那么4、6、8。。。。一系列数都不用判断了,因为2是后面一系列数的公因子,如果连2都除不开,还想除开后面的显然是不可能的。同理,判断完3,那6、9、12、15。。。。。。。一系列数也不用判断了。说白了,只要可拆的数都不用判断,因为我们之前判断过他的某个因子了。也就是只要是合数就没i要判断。
(原本对于单纯的给定一个数,判断是否是素数,这一条意义不大,毕竟我们无法知晓比给定数字小的素数有哪些,但是这里由于要求和,这一条就有意义了,后面举例说明)

2、对于一个数字n,我们究竟验证因子时,验证到多大的时候就可以确定这个数字是素数了呢?答案是n开平方。
解释下原因。假设n是合数,那么n必然能拆成为2个因子相乘n=a*b,a和b均不为1。我们验证的时候极限位置是什么呢,应该是“n的最小因子,最大可能取的值”,这个值刚好就是n开平方。
如果这样说不理解,用另外的方法说明,我们找到a和b中比较小的那个数字,不妨假设a是比较小的,我们让a大于根号n,由于设定上b要大于等于a,所以b大于根号n,两个大于根号n的数相乘,所以a*b是大于n的,与提干等于n矛盾,反证法证明,这两个因子中,最小的那个一定不会超过根号n,极限条件是a和b同时取根号n。也就是说,当我们验证因子的时候,如果验证到了根号n,依然没有找到因子,就说明这个数没有最小因子(除1以外),能拆则必然有最小,哪怕是两个因子相等,那也是两个因子都是最小因子,找不到最小因子,意味着不能拆,也就意味着没有因子,是素数。
我们平时使用的验证方法其实是以找n 最大因子的最大极限来判断的。

这里综合上面两个方法举个例子。
比如验证29。首先根号29=5,所以我们要验证的仅仅5以内的素数是否是29的因子。之前我们每次检测到一个素数都要放入一个集合中,这个集合中小于等于5的数有2、3和5,所以只需验证这3个因子,验证完发现他们都不是29的因子,那么得出结论,29是素数,然后把它丢到素数集合中去

结合上面两条,求1~n内所有素数的和,采用如下方法:
1、首先定义一个集合来存放检索到的素数(定义数组也可以,不过数组长度要足够长,又不要过分长,我们可以用n/(ln n)-1来作为这个数组的长度)
2、搜索素数填入集合中,检索方式采用上面说的
3、计算1集合中所有元素的和(采用数组的话就可以添加是否为0的判断来终止求和,毕竟素数不会装满1中数组的)

代码一会儿贴下

评分

参与人数 1技术分 +1 收起 理由
追溯客 + 1

查看全部评分

回复 使用道具 举报
本帖最后由 大虾挂了 于 2013-11-3 06:04 编辑
  1. using System;
  2. using System.Collections.Generic;

  3. namespace 求1_n的所有素数和
  4. {
  5.     class Program
  6.     {
  7.         static void Main(string[] args)
  8.         {
  9.             //定义一个集合来存放素数,初始状态给集合填入一个2
  10.             List<int> sushu = new List<int>();
  11.             sushu.Add(2);

  12.             Console.WriteLine("请输入一个大于2的数,我们将给出小于等于这个数的所有素数的和");
  13.             int n = Convert.ToInt32(Console.ReadLine());
  14.             //j作为内层循环中,因子检测的sushu集合中的索引.ans用于存储结果
  15.             int j = 0,ans=0;

  16.             for (int i = 3; i < n + 1; i++)
  17.             {
  18.                 //一个数的最小因子,最大不会超过这个数开平方,所以这个数开平方即是验证因子的极限
  19.                 for (j=0; sushu[j] <= Math.Sqrt(i); j++)
  20.                 {
  21.                     //如果这个数能整除集合中的某个数,则证明这个数是合数
  22.                     if (i % sushu[j] == 0)
  23.                         break;
  24.                 }
  25.                 //如果上面的循环没有通过break跳出,下面的条件必然成立,则意味着这个i是素数、
  26.                 //注意,对于3这个素数,根本没有经历过上面循环,这是个特例
  27.                 if (sushu[j] > Math.Sqrt(i))
  28.                     sushu.Add(i);
  29.             }
  30.             //Console.WriteLine("以下是满足条件的所有素数");
  31.             //foreach (int a in sushu)
  32.             //{
  33.             //    Console.Write(a.ToString() + "\t");
  34.             //}
  35.             for (int i = 0; i < sushu.Count; i++)
  36.             {
  37.                 ans+=sushu[i];
  38.             }
  39.             Console.Write("小于等于{0}的所有素数的和为:",n.ToString());
  40.             Console.WriteLine(ans);
  41.             Console.ReadKey();
  42.         }
  43.     }
  44. }
复制代码
这是用我上面说的思路写的代码

评分

参与人数 1技术分 +1 收起 理由
陈福军 + 1

查看全部评分

回复 使用道具 举报
class Program
    {
        static void Main(string[] args)
        {
            int sum = 0;
            for (int i = 2; i <= 100; i++)//因为1不为质数,所以从i从2开始,到100结束,规避了1
            {
                for (int j = 2; j <= i; j++)//j与每次提出来的i进行计算,j从头到尾只能是i的最小值到当前要计算的i的值
                {
                    if (i % j == 0 && i != j)//质数的判断,如果i与从小到大的j整除,并且i不等于j(规避了1),只要有一次满足上边的条件,就能说明i必然不是质数就没必要
                    //继续整除了,试下一个i就行
                    {
                        break;
                    }
                    else if (i == j)      //在判断上边的条件同时(不能是否则,会重复输出)判断下面的条件,显然无论多少次循环只可能有一次满足条件,就是当ij相除所有数都不满足上                                                 // 面的条件,到了
                        //循环最后因为循环条件而结束时,ij必然相等(就是循环结束的条件),这时候的i肯定就是质数了
                        sum = sum + j;
                }
            }
            Console.WriteLine("sum="+sum);
            Console.ReadKey();
        }
    }
穷举法最简单,和是1060
回复 使用道具 举报
            楼上已经写的很好了,因为之前看C语言视频的时候,浙江大学的一个老师讲了一个判断素数的方法,自己觉得比较巧妙吧,想和大家分享一下。
             //求1--100之间所有素数的和
            //质数,又称素数,指在一个大于1的自然数中,除了1和此整数自身外,
            //                无法被其他自然数整除的数
            int sum = 0;
            for (int i = 2; i <= 100; i++)      //循环从2开始,1不是素数,
            {
                int m = (int)Math.Sqrt(i);        //这样效率稍微高点
                int k;
                for (k = 2; k <= m; k++)
                {
                    if (i % k == 0) break;
                }
                //通过结束循环的方式判断是否是素数
                if (k > m) sum = sum + i;
            }
            Console.WriteLine(sum);
            Console.ReadKey();

评分

参与人数 1技术分 +1 收起 理由
追溯客 + 1

查看全部评分

回复 使用道具 举报
  1.         static void Main(string[] args)
  2.         {
  3.             //求100以内素数
  4.             List<int> arr = new List<int>();
  5.             bool flag;
  6.             //忽略偶数
  7.             for (int i = 3; i < 100; i += 2)
  8.             {
  9.                 //判断素数
  10.                 flag = true;
  11.                 foreach (int a in arr)
  12.                 {
  13.                     if (i % a == 0)
  14.                     {
  15.                         flag = false;
  16.                         break;
  17.                     }
  18.                 }
  19.                 if (flag) arr.Add(i);
  20.             }
  21.             //插入第一个素数 2
  22.             arr.Insert(0,2);
  23.             foreach (int i in arr)
  24.             {
  25.                 Console.Write(i + ",");
  26.             }
  27.             Console.WriteLine();
  28.             Console.WriteLine(arr.Sum());
  29.             Console.ReadKey();
  30.         }
复制代码

评分

参与人数 1技术分 +1 收起 理由
陈福军 + 1

查看全部评分

回复 使用道具 举报
本帖最后由 岁月渲染 于 2013-11-3 14:39 编辑

class Program
    {
        static void Main(string[] args)
        {
            int sum = 0;
            for (int i = 1; i < 100; i++)
            {
                if (IsPrime(i) == true) //是否为素数
                {
                    sum = sum + i;
                    Console.WriteLine(i);
                }
            }
            Console.WriteLine("计算1-100之间的所有质数(素数)的和为:{0}",sum);
            Console.ReadKey();
        }
        static bool IsPrime(int n)
        {
            if (n <= 1) return false;
            if (n == 2) return true; //直接判断
            for (int i = 2; i < n / 2; i++)
            {
                if (n % i == 0) return false;
            }
            return true;
        }
    }

运行结果:

QQ截图20131103143020.png (45.46 KB, 下载次数: 55)

QQ截图20131103143020.png

评分

参与人数 1技术分 +1 收起 理由
陈福军 + 1

查看全部评分

回复 使用道具 举报
你可以参考我 以下的方法

  class Program
    {
        static void Main(string[] args)
        {
            int sum = 0;//声明一个变量,求和
            for(int i=1;i<=100;i++)
            {
                if (isZhiShu(i)) //调用判断i是不是质素的方法
                {
                    sum += i;
                }
            }
            Console.WriteLine("1到100之间的素数的和为:"+sum);
            Console.ReadKey();
        }

        /// <summary>
        /// 判断是不是素数的方法
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        static bool isZhiShu(int n)
        {
            if (n < 2)
            {
                return false;
            }
            for (int i = 2; i < (n / 2) + 1; i++)
            {
                if (n % i == 0)
                {
                    return false;
                }
            }
            return true;
        }
    }

评分

参与人数 1技术分 +1 收起 理由
陈福军 + 1

查看全部评分

回复 使用道具 举报
  1. /// <summary>
  2.         /// 计算1-100之间的所有素数和
  3.         /// </summary>
  4.         /// <returns></returns>
  5.         static int GetPrimeSum()
  6.         {
  7.             int sum = 0;
  8.             for (int i = 0; i < 100; i++)
  9.             {
  10.                 if (IsPrime2(i))
  11.                 {
  12.                     sum += i;
  13.                 }
  14.             }
  15.             return sum;
  16.         }
  17.         static bool IsPrime(int number)//判断一个数是否是质数
  18.         {
  19.             if (number < 2)//小于2 不是素数
  20.             {
  21.                 return false;
  22.             }
  23.             else if (number == 2)//等于2是素数
  24.             {
  25.                 return true;
  26.             }
  27.             else
  28.             {
  29.                 for (int i = 2; i < number; i++)//大于2 进行判断
  30.                 {
  31.                     if (number % i == 0)
  32.                     {
  33.                         return false;
  34.                     }
  35.                 }
  36.                 return true;
  37.             }
  38.         }
复制代码

评分

参与人数 1技术分 +1 收起 理由
追溯客 + 1

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马