c#求素数！！！！！

Question

输出456以内的素数！  
初学，请多指点哈！  
希望有多种方法！  
谢谢

Answer 1

[转贴]
using System;
using System.Collections.Generic;
using System.Text;namespace DataStructure
{
    
    public class Prime
    {
        private static List _prime=new ArrayList();
        /// <summary>
        /// check prime
        /// </summary>
        /// <param name="a"></param>
        /// <returns></returns>
        public static bool isPrime(int a)
        {
            int i;
            for (i = 2; i < a; i++)
            {
                if (Math.IEEERemainder((float)a, (float)i) == 0) //是否能被i整除
                    return false;
            }
            return true;
        }
        /// <summary>
        /// get all prime
        /// </summary>
        /// <param name="min"></param>
        /// <param name="max"></param>
        /// <returns></returns>
        public static List getPrime(int min, int max)
        {
            if (min < 1)
                throw new Exception("min must greater than 1");
            int i;
            for (i = min; i <= max; i++)
            {
                if (isPrime(i))
                    _prime.add(i);
            }
            return _prime;
        }
        /// <summary>
        /// print all prime
        /// </summary>
        public static void printPrime()
        {
            _prime.print();
        }
    }
}
测试：
            Prime.getPrime(2, 60);
            Prime.printPrime();结果：2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59

Answer 2

List<int> Prime = new List<int>();
            Prime.Add(2);            for (int i = 2; i < 500; i++)
            {
                bool isPrime = true;                for (int j = 0; j < Prime.Count; j++)
                {
                    if (i % Prime[j] == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }                if (isPrime)
                {
                    Prime.Add(i);
                }
            }            string output = string.Empty;
            for (int i = 0; i < Prime.Count; i++)
            {
                output += Prime[i].ToString() + ",";
            }            output = output.Substring(0, output.Length - 1);
            MessageBox.Show(output);

Answer 3

真的是初学的,比如:List<int> Prime = new List<int>();
            Prime.Add(2);
这个东西,真的没有见过! ???

Answer 4

用链表的算法
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449  Counts=872一定是素数，把2的倍数筛除
下一个一定是素数，把这个数的倍数筛除
直到链表结束，正好得到所有素数int upper=456
            LinkedList<int> llPrimaryNumbers = new LinkedList<int>();
            for (int i = 2; i <= upper; i++) llPrimaryNumbers.AddLast(i);            LinkedListNode<int> pCurrentPrimary = llPrimaryNumbers.First;
            do
            {
                //AppendOutputs(pCurrentPrimary);
                LinkedListNode<int> pLookThrough = pCurrentPrimary.Next;
                while (!(pLookThrough == null))
                {
                    if (pLookThrough.Value % pCurrentPrimary.Value == 0)
                    {
                        LinkedListNode<int> pRemove = pLookThrough;
                        pLookThrough = pLookThrough.Next;
                        llPrimaryNumbers.Remove(pRemove);
                    }
                    else
                    {
                        pLookThrough = pLookThrough.Next;
                    }
                }
                pCurrentPrimary = pCurrentPrimary.Next;
            } while (!(pCurrentPrimary == null));

Answer 5

我为楼主注释了一下。            // 新建链表
            LinkedList<int> llPrimaryNumbers = new LinkedList<int>();
            // 初始化链表：假定比2大的所有数都有可能是素数（后面一个个地干掉）
            for (int i = 2; i <= upper; i++) llPrimaryNumbers.AddLast(i);            // 从第一个素数(2)开始，筛数TA的倍数
            LinkedListNode<int> pCurrentPrimary = llPrimaryNumbers.First;
            do
            {
                AppendOutputs(pCurrentPrimary); // 输出,你可以用Console.Write("{0} ",pCurrentPrimary.Value);
                //从当前的素数下一个开始看
                LinkedListNode<int> pLookThrough = pCurrentPrimary.Next;
                while (!(pLookThrough == null))
                {
                    // 能否被当前素数整除
                    if (pLookThrough.Value % pCurrentPrimary.Value == 0)
                    {
                        // 干掉这个能被整除的
                        LinkedListNode<int> pRemove = pLookThrough; // 防止删掉了自己就取不到Next了
                        pLookThrough = pLookThrough.Next;
                        llPrimaryNumbers.Remove(pRemove); // 从链表中删除
                    }
                    else
                    {
                        // 不能整除，看下一个
                        pLookThrough = pLookThrough.Next;
                    }
                }
                // 取下一个素数（为什么下一个一定是素数呢？自己想，用手算一下就知道）
                pCurrentPrimary = pCurrentPrimary.Next;
            } while (!(pCurrentPrimary == null));
            // 输出个数：Console.WriteLine("Counts={0}",llPrimaryNumber.Count);
            OutputCounts(llPrimaryNumbers.Count);

Answer 6

可以改进一下,事实上,测试到一个数字的一半就够了,再大的不用测试,原理就不用说了吧 
public static bool isPrime(int a) 
{ 
int i; 
//int iEnd = a/2 + 1; 
//for(i=2; i<iEnd; i++) 
for (i = 2; i <= a/2; i++) 
{ 
if ( a/i == 0) //是否能被i整除 
return false; 
} 
return true; 
} 感觉用Math.IEEERemainder((float)a, (float)i)并不好,类型转换划不来,直接除就行了,在条件中已经排除除数为0的情况了,所以不用担心

Answer 7

楼主要能看懂的我也写一个。这个时间性能要差一些。但是不要保存，空间性能比较好。
using System;
using System.Collections.Generic;
using System.Text;namespace ConsolePrime
{
    class Program
    {
        static void Main(string[] args)
        {
            int upper=456;
            
            PrimersLessThan(upper);
        }
        static int PrimersLessThan(int upper)
        {
            int counts = 0;
            for(int prime=2; prime<upper; prime++)
            {
                if ( IsPrime(prime) )
                {
                    counts++;
                    Console.Write("{0} ", prime);
                }
            }
            Console.WriteLine();
            Console.WriteLine("Total prime numbers less than {0} is {1}",upper,counts);
            return counts;
        }
        static bool IsPrime(int p)
        {
            for (int lookThrough = 2; lookThrough <= Math.Sqrt((double)p); lookThrough++)
            {
                if (p % lookThrough == 0)
                    return false;
            }
            return true;
        }
    }
}

Answer 8

上面那个有个小BUG....如果upper本身是素数的话会出问题。
把for(int prime=2; prime<upper; prime++)改成prime<=upper就可以了。