Nerd-sniped. APL algorithm for frindin primes is elegant but wasteful, can do better? 2 new messages since 1:28 PM Mark as read (esc)Mark as read Channel #tech

WTFAPL.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 7]\n"
     ]
    }
   ],
   "source": [
    "def wtfapl(n):\n",
    "    '''\n",
    "    See https://en.wikipedia.org/wiki/APL_(programming_language)#Prime_numbers\n",
    "    '''\n",
    "    R = range(2, n+1)\n",
    "    M = [n*m for n in R for m in R]\n",
    "    E = [int(i in M) for i in R]\n",
    "    E = [int(not i) for i in E]\n",
    "    return [r for e, r in zip(E, R) if e]\n",
    "\n",
    "print wtfapl(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Thu(object):\n",
    "    '''\n",
    "    We want a thing that takes a generator and a callback and provides a function that, when you call it with an\n",
    "    int, it returns True if the int is in the generator, from the current value (starts at first value from G) to\n",
    "    the next value higher than it.  (Assumed G is strictly growing.)  The closure keeps track of the current\n",
    "    value.\n",
    "    '''\n",
    "    \n",
    "    def __init__(self, G, cb):\n",
    "        self.G = G  # Remeber the generator.\n",
    "        self.cb = cb  # Remember the callback.\n",
    "        self.x = 0\n",
    "        \n",
    "    def __call__(self, n):\n",
    "        while self.x < n:  # Iterate up to or over n.\n",
    "            try:\n",
    "                self.x = next(self.G)\n",
    "            except StopIteration:\n",
    "                return False\n",
    "            self.cb(self.x)  # All values must be given to the callback.\n",
    "        return n == self.x  # Did we find n?\n",
    "\n",
    "\n",
    "def X(R):\n",
    "    return xrange(2, R + 1)\n",
    "\n",
    "def g(n, R):\n",
    "    return (n * r for r in X(R))\n",
    "\n",
    "def h(R):\n",
    "    return (g(n, R) for n in X(R))\n",
    "\n",
    "def find_primes(R):\n",
    "    s = set()\n",
    "    Ts = [lambda n: n in s] + [Thu(gu, s.add) for gu in h(R)]\n",
    "    F = lambda n: not any(f(n) for f in Ts)\n",
    "    return (n for n in X(R) if F(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "5\n",
      "7\n",
      "11\n",
      "13\n",
      "17\n",
      "19\n",
      "23\n"
     ]
    }
   ],
   "source": [
    "for n in find_primes(25):\n",
    "    print(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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": 1
}