`

判断质数以及求某数以内的质数

阅读更多
xml 代码
  1.        今天去笔试,做了个关于求某数以内质数之和的题目,虽然做出来了,但是感觉效率还是很低,不过查了下,也没其他的效率高的方法(也许是baidu没用好的缘故)。先把自己的与大家一起分享,有什么建议希望大家不吝赐教。   
  2. #include<iostream.h>  
  3. #include <stdlib.h>  
  4. int main()   
  5. {   
  6.  //该程序可以用来判断一个数是否是质数,以及求出小于某个数范围之内的所有的质数   
  7.     
  8.  int w;//保存要测试的数   
  9.  int q;//保存判断的值   
  10.  cout<<"请输入测试的数"<<endl;   
  11.  cin>>w;   
  12.     
  13.  cout<<"是否判断,是就输入1,不是就任意输入"<<endl;   
  14.  cin>>q;   
  15.  int e=0;//保存质数的个数   
  16.     
  17.     
  18.  for(int i=2;i<w+1;i++) //被除数的遍历   
  19.  {    
  20.   if(q==1){//表明是用来判断的   
  21.    i=w;   
  22.   }   
  23.   int c=0; //保存整除因数的个数   
  24.   for(int j=2;j<w+1;j++)//除数遍历   
  25.   {    
  26.       
  27.    if(i%j==0)//整除   
  28.    {   
  29.      c++;   
  30.    }   
  31.   }   
  32.   if(c==1)//表明只有一个整数因子   
  33.   {   
  34.    cout<<i<<"是质数"<<endl;   
  35.    e++;   
  36.   }   
  37.   if(q==1){   
  38.    if(c!=1)   
  39.    {   
  40.     cout<<i<<"不是质数"<<endl;   
  41.    }   
  42.    break;   
  43.   }   
  44.  }   
  45.  if(e>0)   
  46.   cout<<"共有"<<e<<"个质数"<<endl;   
  47. system("PAUSE");//系统函数,包含在<stdlib.h>头文件中,用于暂停屏幕   
  48.  return 0;   
  49. }   
  50.     
  51. 该程序在VC6.0环境下测试的能够正常运行。如果你提出那个2层循环用平方根代替以前的数能够提高效率,的确这样也可以,我好久没用C++了,所以平方的函数忘了,如果你想这样做也可以试下。  
分享到:
评论
3 楼 stworthy 2008-01-26  
<p>来个Erlang版本的:</p><pre name='code' class='java'>-module(test).
-export([main/1]).

main(N) -&gt;
    L = calc(N, []),
    S = lists:foldl(fun(X, Total) -&gt; Total+X end, 0, L),
    io:format("质数:~p~n", [L]),
    io:format("总和:~p~n", [S]).
   
%统计某个数以内的所有质数
calc(1, L) -&gt; L;
calc(N, L) -&gt;
    case is_single(N) of
        false -&gt; calc(N-1, L);
        true -&gt; calc(N-1, [N|L])
    end.

%判断是否是质数
is_single(N) -&gt; is_single(N, N-1).
is_single(_N, 1) -&gt; true;
is_single(N, D) when N rem D ==0 -&gt; false;
is_single(N, D) -&gt; is_single(N, D-1).
</pre><p> </p>
2 楼 抛出异常的爱 2008-01-22  
package com.maodajun.javaeye5;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class SingleWord {
	List list = new ArrayList();
	/**
	 * 将list中的数据求合
	 * @return
	 */
	public int addAll(){
		int all = 0 ;
		String temp = null;
		for(Iterator it = list.iterator();it.hasNext();){
			temp = (String) it.next();
			all += Integer.parseInt(temp);
		}
		return all;
	}
	/**
	 * @deprecated
	 * 已过时方法
	 * 用于判断是否是质数
	 * @param str
	 */
	public void isSingle(String str){
		int tmp = Integer.parseInt(str);
		if(tmp<2){
			return;
		}
		for(int i = 2 ; Math.sqrt(tmp) >=i ; i ++ ){
			if(tmp%i==0){
				return;
			}
		}
		list.add(str);
	}
	/**
	 * 用来找到所有小于str的质数方法
	 * 
	 */
	public void findAllSingle(String str){
		int tmp = Integer.parseInt(str);
		for(int i = 0 ; tmp >i ;i ++){
			isOldSingle(""+i);
		}
	}
	/**
	 * 对输入的数值与已有的数值对比
	 * 看可否被整除.
	 * 
	 * @param str
	 */
	public void isOldSingle(String str){
		int tmp = Integer.parseInt(str);
		if(tmp<2){
			return;	
		}else{
			for(int i = 0 ; list.size()>i ;i++ ){
				int single =Integer.parseInt(list.get(i).toString());
				if(tmp%single ==0){
					return;
				}
			}			
		}
		list.add(str);
	}
	public List getList() {
		return list;
	}
	public void setList(List list) {
		this.list = list;
	}

}


package com.maodajun.javaeye5;

import java.util.ArrayList;
import java.util.List;

import junit.framework.TestCase;

public class SingleWordTest extends TestCase {

	public static void main(String[] args) {
		junit.textui.TestRunner.run(SingleWordTest.class);
	}

	public SingleWordTest(String arg0) {
		super(arg0);
	}

	protected void setUp() throws Exception {
		super.setUp();
	}

	protected void tearDown() throws Exception {
		super.tearDown();
	}

	/*
	 * Test method for 'com.maodajun.javaeye5.SingleWord.addAll()'
	 */
	public void testAddAll() {
		List list = new ArrayList();
		list.add("1");
		list.add("2");
		SingleWord singleword = new SingleWord();
		singleword.setList(list);
		int i = singleword.addAll();
		assertEquals(3,i);
	}
	public void testIsSingle(){
		SingleWord singleword = new SingleWord();
		singleword.isSingle("0");
		assertEquals(0,singleword.getList().size());
		singleword.isSingle("1");
		assertEquals(0,singleword.getList().size());
		singleword.isSingle("4");
		assertEquals(0,singleword.getList().size());
		singleword.isSingle("2");
		assertEquals(1,singleword.getList().size());
		singleword.isSingle("3");
		assertEquals(2,singleword.getList().size());
		singleword.isSingle("13");
		assertEquals(3,singleword.getList().size());
		singleword.isSingle("25");
		assertEquals(3,singleword.getList().size());
		
	}
	public void testIsOldSingle(){
		SingleWord singleword = new SingleWord();
		singleword.isOldSingle("0");
		assertEquals(0,singleword.getList().size());
		singleword.isOldSingle("1");
		assertEquals(0,singleword.getList().size());
		singleword.isOldSingle("2");
		assertEquals(1,singleword.getList().size());
		singleword.isOldSingle("3");
		assertEquals(2,singleword.getList().size());
		singleword.isOldSingle("4");
		assertEquals(2,singleword.getList().size());
		singleword.isOldSingle("5");
		assertEquals(3,singleword.getList().size());
		singleword.isOldSingle("6");
		assertEquals(3,singleword.getList().size());
		
	}
	public void testFindAllSingle(){
		SingleWord singleword = new SingleWord();
		singleword.findAllSingle("10");
		assertEquals(17,singleword.addAll());
		singleword .setList(new ArrayList());
		singleword.findAllSingle("20");
		assertEquals(77,singleword.addAll());

	}

}
1 楼 yzfy 2008-01-21  
请使用线性筛法

相关推荐

    1亿以内的质数(共5761455个数).txt_1亿以内素数的个数

    #### 二、1亿以内质数的数量 根据题目给出的信息,1亿以内的质数共有5,761,455个。这一数字不仅展示了质数分布的密集程度,也反映了寻找并验证大范围质数的计算挑战。 #### 三、质数的分布规律 1. **质数分布定理**...

    求素数,回文数,回文素数,可逆素数

    本程序通过编写一系列的辅助函数,实现了对素数、回文数、回文素数以及可逆素数的判断。主函数 `main` 提供了一个菜单界面,用户可以根据提示选择不同的功能选项,从而得到10000以内各种类型的数字列表。这些知识点...

    算法-求一亿以内的回文质数(素数).rar

    或者,利用质数筛法(如埃拉托斯特尼筛法)提前筛选出所有1亿以内的素数,再进行回文判断。 这个任务不仅涉及基础的算法和数据结构,还考验了编程效率和内存管理。通过解决这个问题,可以提升编程技巧,理解并实践...

    求出1000以内的素数及素数的个数

    具体来说,对于每一个数n,通过检查其是否有除了1和自身以外的因数来进行素数判断。为了提高效率,检查的上限设定为sqrt(n),这是因为如果n有一个因子大于sqrt(n),那么必然存在另一个因子小于等于sqrt(n)。 ### 二...

    用python编写代码找出1000以内的素数和双素数

    用python编写代码找出1000以内的素数和双素数 一、素数 素数(prime number)又称质数,有无限个。除了1和它本身外,不能被其他自然数整除。换句话说就是该数除了1和它本身以外不再有其他的因数的数。 注意:最小的...

    使用SAS计算某个整数内所有素数

    通过写SAS宏程序,使用循环语句搜索某个整数内所有的素数

    100以内判断素数.py

    100以内判断素数.py

    求100以内的素数

    #### 三、求解100以内素数的算法实现 - **核心思路**: - 对于每个数`i`(从2到100),检查其是否为素数。 - 使用一个变量`jishu`记录是否找到因子,初始值设为1表示当前数可能是素数。 - 计算每个数的平方根`...

    MIPS汇编下用筛选法求100以内素数

    MIPS汇编语言下使用筛选法求100以内素数 本节将介绍使用MIPS汇编语言实现筛选法求100以内素数的方法,并与C语言对照,以便读者更好地理解。 MIPS汇编语言基础 MIPS(MIPS Instruction Set)是一种RISC(Reduced ...

    水仙花数100以内素数判断素数(精).pdf

    "水仙花数100以内素数判断素数(精)" 水仙花数是一种特殊的数字,它满足自身的各位数字的立方和等于该数字本身。例如,153是一个水仙花数,因为1^3 + 5^3 + 3^3 = 153。以下是关于水仙花数和素数的知识点: 一、...

    求出10万以内的所有素数,并输出到 一个文本文件中,每行文本只包含一个素数数据;然后再判断这些素数中哪些是由素数拼接而成的,全部打印出来,并统计个数。

    2. 编写程序求出10万以内的所有素数,然后再判断这些素数中 哪些是由素数拼接而成的。例如素数23就符合条件, 23本身是素数,其由素数2,和素数3拼接(连接)组成。 素数29就不满足条件,2是素数,而9不是素数。 ...

    C# 判断一个数是否为素数

    本篇文章将深入探讨如何使用C#来判断一个数是否为素数,这不仅是对C#语言基础技能的实践,也是对算法理解的深化。 ### C# 判断一个数是否为素数 #### 知识点一:素数定义 首先,了解什么是素数非常重要。素数...

    LabView 计算整数N内所有的素数

    判断一个数是否为素数是计算机科学中的基础算法之一。以下是一些关于这个主题的重要知识点: 1. **素数定义**:理解素数的概念是编程求解的基础。素数不包括1和0,且大于1的自然数如果只有两个正因数1和本身,那么...

    用汇编语言求1000以内的质数

    根据给定的文件信息,我们可以总结出以下与“用汇编语言求1000以内的质数”相关的知识点。 ### 汇编语言简介 汇编语言是一种低级编程语言,它为每条机器指令提供一个助记符,使得程序员能够更容易地编写程序,并且...

    求1000以内的素数

    这种方法的基本思想是,对于每一个待判断的数字n,我们从2开始依次尝试将其除以小于等于它的所有正整数,如果没有找到能整除n的数,那么n就是素数。 下面是一个简单的C++代码示例来实现这个算法: ```cpp #include...

    输出n以内的所有素数 c语言:找出N以内的所有素数

    输出n以内的所有素数c语言:找出N以内的所有素数 输出n以内的所有素数是c语言中的一种常见算法题,旨在找到小于或等于n的所有素数。该算法有多种实现方法,本文将介绍两种常见的方法。 方法一: 筛选法 该方法的...

    第二次作业:求100以内的素数_素数_

    本篇我们将深入探讨如何使用C++语言编写程序来寻找100以内的所有素数。 首先,我们需要理解素数的基本概念和判断方法。对于一个给定的整数n,我们可以通过以下步骤来判断它是否为素数: 1. **基本检查**:如果n...

    求1000以内的质数C++程序

    通过以上分析,我们可以看到原程序虽然基本实现了求1000以内质数的功能,但在细节处理上存在一定的问题。理解质数的概念及其判断方法对于编写正确的程序至关重要。同时,在编程实践中,需要注意代码的逻辑清晰度和...

    求n以内的素数并用数组存储

    键盘输入n,判断n以内的素数,存入数组内输出。

    输出10000以内的质数判断区间内的质数.docx

    在C语言的学习过程中,开发一个程序来找出10000以内的质数,并判断用户指定区间内是否存在质数是一项常见的练习。这个程序的核心在于理解质数的概念以及如何有效地检查一个数是否为质数。质数是大于1的自然数,除了1...

Global site tag (gtag.js) - Google Analytics