{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 声明\n", "本源码为[浚宇的博客](http://blog.junyu.pro)博文中代码源码，欢迎下载、交流，请标明出处。\n", "\n", "## 基础办法" ] }, { "cell_type": "code", "execution_count": 78, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import numpy as np" ] }, { "cell_type": "code", "execution_count": 79, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "100 is not a prime\n" ] } ], "source": [ "\n", "# x = int(raw_input(prompt='please insert a number'))\n", "x = 100\n", "is_prime=0\n", "for i in range(2,x):\n", " if x % i == 0:\n", " is_prime = 0\n", " break\n", "else:\n", " is_prime = 1\n", "if is_prime==0:\n", " print \"%d is not a prime\" %x\n", "if is_prime==1:\n", " print \"%d is a prime\" %x" ] }, { "cell_type": "code", "execution_count": 80, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1060\n" ] } ], "source": [ "# x = int(raw_input(prompt='please insert a number'))\n", "x = 100\n", "is_prime=0\n", "sum=0\n", "\n", "for j in range(2,x):\n", " for i in range(2,j):\n", " if j % i == 0:\n", " is_prime = 0\n", " break\n", " else:\n", " is_prime = 1\n", " sum += j\n", "print sum" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 利用数学知识" ] }, { "cell_type": "code", "execution_count": 81, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def is_prime(x):\n", " for i in range(2,int(x**(1/2.)+1)):\n", " if x % i == 0:\n", " is_prime_flag = 0\n", "# print \"it is not a prime\"\n", " break\n", " else:\n", " is_prime_flag = 1\n", "# print \"it is a prime\"\n", " return is_prime_flag" ] }, { "cell_type": "code", "execution_count": 82, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def prime_sum(num):\n", " sum = 0\n", " for sum_i in range (2,num):\n", " if is_prime(sum_i):\n", " sum += sum_i\n", " return sum" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Numpy库实现" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def is_prime_v(x):\n", " a = np.arange(1,x+1)\n", " b = a.reshape(x,1)\n", " c = a % b\n", " d = np.where(c>0,0,1)\n", " e = d.sum(axis = 0)\n", " f = np.where(e!=2,0,1)\n", " g = (f*a).sum()\n", " return g\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 向量方法\n" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def judge_prime(x):\n", " for i in range(2,int(x**(1/2.)+1)):\n", " if x % i == 0:\n", " is_prime_flag = 0\n", " return False\n", " return True\n", "\n", "\n", "\n", "\n", "def sum_prime_v(y):\n", " arr = np.arange(1,y+1)\n", " v = np.vectorize(judge_prime)\n", " return arr[v(arr)].sum()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 效率计算\n", "注意：方法1的效率计算需要先封装为函数，后面的处理才比较方便" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def method1(x):\n", " is_prime=0\n", " sum=0\n", " for j in range(2,x):\n", " for i in range(2,j):\n", " if j % i == 0:\n", " is_prime = 0\n", " break\n", " \n", " else:\n", " is_prime = 1\n", " sum += j\n", " return sum" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 先验证结果，再验证效率" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def printout(x):\n", " x1 = method1(x)\n", " x2 = prime_sum(x)\n", " x3 = is_prime_v(x)\n", " x4 = sum_prime_v(x)\n", " print \"方法1的结果是 %d\" %x1\n", " print \"方法2的结果是 %d\" %x2\n", " print \"方法3的结果是 %d\" %x3\n", " print \"方法4的结果是 %d\" %x4" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "方法1的结果是 76127\n", "方法2的结果是 76127\n", "方法3的结果是 76127\n", "方法4的结果是 76128\n" ] } ], "source": [ "printout(1000)" ] }, { "cell_type": "code", "execution_count": 73, "metadata": { "collapsed": true }, "outputs": [], "source": [ "y = 10000" ] }, { "cell_type": "code", "execution_count": 74, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 loops, best of 3: 1.73 s per loop\n" ] } ], "source": [ "%timeit -n10 method1(y)" ] }, { "cell_type": "code", "execution_count": 75, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 loops, best of 3: 44.6 ms per loop\n" ] } ], "source": [ "%timeit -n10 prime_sum(y)" ] }, { "cell_type": "code", "execution_count": 76, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 loops, best of 3: 2.65 s per loop\n" ] } ], "source": [ "%timeit -n10 is_prime_v(y)" ] }, { "cell_type": "code", "execution_count": 77, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 loops, best of 3: 40.8 ms per loop\n" ] } ], "source": [ "%timeit -n10 sum_prime_v(y)" ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python [Root]", "language": "python", "name": "Python [Root]" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.12" } }, "nbformat": 4, "nbformat_minor": 0 }