C++, 34 bits

#include <algorithm>
#include <array>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <string>

#include <unistd.h>

using u8 = uint8_t;
using u32 = uint32_t;
using u64 = uint64_t;

const u8 N = 34;
const u64 M = 1ull << N;
const u32 S = M >> (N / 2);

const u8 lo = (N + 1) / 2 + 1;
const u8 hi = N - lo;

char buf[524288];
char *buf_ptr = buf;

constexpr auto two = []() {
  std::array<char, 5 * N - 1> ret{'('};
  for (int i = 0; i < N; i++) {
    ret[i * 5 + 1] = '(';
    ret[i * 5 + 2] = '~';
    ret[i * 5 + 3] = i < 26 ? 'A' + i : 'a' + i - 26;
    if (i != N - 1) {
      ret[i * 5 + 4] = ')';
      ret[i * 5 + 5] = '&';
    }
  }

  ret[5 + 2] = ' ';

  return ret;
}();

constexpr auto tmpl_lo = []() {
  std::array<char, 5 * (lo - 1) + 2> ret{'|', '('};
  std::string base("(  )&");

  for (int i = 0; i < lo - 1; i++) {
    base.copy(ret.data() + i * 5 + 2, base.size());
    ret[i * 5 + 4] = i + 1 < 26 ? 'A' + i + 1 : 'a' + i + 1 - 26;
  }

  ret[5 * (lo - 1) + 1] = ')';

  return ret;
}();

constexpr auto tmpl_hi = []() {
  std::array<char, 5 * hi + 11> ret{')', ')', '|', '('};
  std::string base("(  )&");

  for (int i = 0; i < hi; i++) {
    base.copy(ret.data() + i * 5 + 4, base.size());
    ret[i * 5 + 6] = lo + i < 26 ? 'A' + lo + i : 'a' + lo + i - 26;
  }

  std::string end("A&((~A)");
  end.copy(ret.data() + 5 * hi + 4, end.size());

  return ret;
}();

void flush() {
  write(1, buf, buf_ptr - buf);
  buf_ptr = buf;
}

template <size_t N> void output(std::array<char, N> s) {
  if (buf_ptr - buf + s.size() >= 524288)
    flush();
  memcpy(buf_ptr, s.data(), s.size());
  buf_ptr += s.size();
}

void output_lo(u32 x) {
  if (buf_ptr - buf + tmpl_lo.size() >= 524288)
    flush();
  memcpy(buf_ptr, tmpl_lo.data(), tmpl_lo.size());
  for (u32 i = 0; i < lo - 1; i++)
    buf_ptr[i * 5 + 3] = (x >> i) & 1 ? ' ' : '~';
  buf_ptr += tmpl_lo.size();
}

void output_hi(u32 x) {
  if (buf_ptr - buf + tmpl_hi.size() >= 524288)
    flush();
  memcpy(buf_ptr, tmpl_hi.data(), tmpl_hi.size());
  for (u32 i = 0; i < hi; i++)
    buf_ptr[i * 5 + 5] = (x >> i) & 1 ? ' ' : '~';
  buf_ptr += tmpl_hi.size();
}

template <u32 N> constexpr auto sieve_helper() {
  constexpr auto sieve = []() {
    std::array<bool, N> ret{};
    for (u32 i = 3; i < N; i += 2)
      if (!ret[i])
        for (u32 j = i * i; j < N; j += 2 * i)
          ret[j] = true;
    return std::make_pair((N - 2) / 2 - std::count(ret.begin(), ret.end(), true), ret);
  }();

  std::array<std::pair<u32, u64>, sieve.first> ret;
  for (u32 i = 3, j = 0; i < N; i += 2)
    if (!sieve.second[i])
      ret[j++] = {i, ((u64)i * i - 1) / 2};
  return ret;
}

int main() {
  output(two);

  auto small = sieve_helper<S + 1>();

  std::array<bool, S> block;
  for (u64 low = 0, high = (M - 1) / 2; low <= high; low += S) {
    output_hi(low / S);

    std::fill(block.begin(), block.end(), true);
    for (auto &[i, j] : small) {
      for (; j < S; j += i)
        block[j] = false;
      j -= S;
    }

    block[0] &= low != 0;
    for (u32 i = 0; i < S; i++)
      if (block[i])
        output_lo(i);
  }

  output(std::array<char, 2>{')', ')'});

  flush();
}

Attempt This Online! (10 bit version)
Verify output for 10 bits

Uses the character A-Za-z to represent the bits where A is the lsb and z is the msb.

Generates a boolean expression which brute-force checks every prime it is slightly more optimized now by grouping the high bits, the expression is ~60GiB.

Uses a segmented sieve for better cache locality, should also make it easy to have it use multiple cpu cores might get around to doing that at some point.

$ g++ -std=c++23 -Ofast -march=native a.cpp

$ time ./a.out | wc -c
66381666517
./a.out  23.00s user 5.17s system 82% cpu 34.010 total
wc -c  0.16s user 6.16s system 18% cpu 34.010 total

$ time ./a.out >/dev/null
./a.out > /dev/null  21.30s user 0.01s system 99% cpu 21.342 total

JavaScript, 18 bits

let numBits = 23;
let smallestFactor = new Array(2**numBits + 1);
smallestFactor.fill(0);
let primes = [];
let str = "";

for (let i = 2; i <= 2**numBits; ++i) {
    if (smallestFactor[i] == 0) {
        smallestFactor[i] = i;
        primes.push(i);
        str += "("
        for (let j = 0; j < numBits; j++){
            if (i & (1 << j)){
                str += "(¬" + (numBits - j) + ((j != numBits - 1) ? ")&" : "))|");
            }else{
                str += (numBits - j) + ((j != numBits - 1) ? "&" : ")|");
            }
        }
    }
    for (let j = 0; i * primes[j] <= 2**numBits; ++j) {
        smallestFactor[i * primes[j]] = primes[j];
    }
}
console.log(str.substring(0,str.length - 1));

The code works by filtering out the primes in the range [0,2^numBits], using the Sieve of Eratosthenes. It converts these primes to binary, and makes a sort of truth table, matching prime binary numbers to 1, and everything else to 0. I then used SOP to fit a boolean expression to this truth table. Here is an example of SOP on a 3-digit prime number table.

Number | Is prime?
==================
000    |0
001    |0
010    |1
011    |1
100    |0
101    |1
110    |0
111    |1

Prime when number = 010 | 011 | 101 | 111

Checking if the number is just one of these cases, 010 for example, can be expanded to (digit 1 = 0) & (digit 2 = 1) & (digit 3 = 0). This can be written more concisely as ((¬d1) & d2 & (¬d3)). Doing this for each case, we get ((¬d1) & d2 & (¬d3)) | ((¬d1) & d2 & d3) | (d1 & (¬d2) & d3) | (d1 & d2 & d3).

Edit February 23rd: Used this article to massively improve the time complexity of the algorithm.

30 bits

#include <iostream>
#include <string>
const int N = 30;
char primes[1<<(N-1)];
template<int k>
void f(int x) {
    std::cout << "(("<<k<<"&(";
    f<k-1>(x+(1<<(k-1)));
    std::cout << "))|(¬"<<k<<"&(";
    f<k-1>(x);
    std::cout << ")))";
}
template<>
void f<6>(int x) {
    bool empty = 1;
    for (int i=0; i<32; ++i) {
        if (!primes[i]) {
            if (!empty) std::cout << '|';
            empty = 0;
            std::cout << ((i&16)?"(6":"((¬6)");
            std::cout << ((i&8)?"&5":"&(¬5)");
            std::cout << ((i&4)?"&4":"&(¬4)");
            std::cout << ((i&2)?"&3":"&(¬3)");
            std::cout << ((i&1)?"&2)":"&(¬2))");
        }
    }
    if (empty) std::cout << "(¬1))";
}
int main() {
    std::ios::sync_with_stdio(false);
    // 2 is a prime
    std::cout << "(2";
    for (int i=3; i<=N; ++i) std::cout << "&(¬" << i << ')';
    std::cout << ")|(1&(";
    // prime init
    primes[0] = 1;
    for (int i=1; i<sizeof primes; ++i) {
        if (!primes[i]) { //std::cout << 2*i+1 << ',' << i << '\n';
            for (int j=i; (j+=2*i+1)<sizeof primes; ) {
                primes[j] = 1;
            }}}
    f<N>(0);std::cout << "))";
}

Executing result

$g++ -O2 278146.cpp && time ./a.out | wc
      0       1 6513754292

real    0m54.601s
user    1m27.957s
sys 0m2.918s

Seems time also count time of wc

verifier for N=8

Rust, 18 bits

Rust port of @DesmosEnthusiast's JavaScript answer.

You can run n=10 case at RustPlayground!

fn main() {
    let num_bits: i128 = 18;
    let mut primes: Vec<Vec<char>> = Vec::new();
    let mut not_prime: Vec<i128> = vec![0, 1];

    if num_bits > 1 {
        // Use checked_pow for overflow protection
        let limit = match 2_i128.checked_pow(num_bits as u32) {
            Some(value) => value,
            None => {
                println!("2^{} overflows i128", num_bits);
                return;
            }
        };

        for i in 0..limit {
            if !not_prime.contains(&i) {
                let mut binary: Vec<char> = format!("{:b}", i).chars().collect();
                if binary.len() < num_bits as usize {
                    let mut filler = vec!['0'; num_bits as usize - binary.len()];
                    filler.append(&mut binary);
                    binary = filler;
                }
                primes.push(binary);

                // Use checked_mul and checked_add for overflow protection
                let square = match i.checked_mul(i) {
                    Some(value) => value,
                    None => {
                        println!("Overflow in square calculation for {}", i);
                        continue;
                    }
                };
                
                let mut j = square;
                while j < limit {
                    not_prime.push(j);
                    j = match j.checked_add(i) {
                        Some(value) => value,
                        None => {
                            println!("Overflow in increment for i={}", i);
                            break;
                        }
                    };
                }
            }
        }
    }

    let mut rule = String::new();
    for (i, prime) in primes.iter().enumerate() {
        let mut number_rule = String::from("(");
        for (j, &digit) in prime.iter().enumerate() {
            if digit == '0' {
                number_rule.push_str(&format!("(¬d{})", j + 1));
            } else {
                number_rule.push_str(&format!("d{}", j + 1));
            }
            if j != num_bits as usize - 1 {
                number_rule.push_str(" & ");
            }
        }
        rule.push_str(&number_rule);
        rule.push(')');
        if i != primes.len() - 1 {
            rule.push_str(" | ");
        }
    }
    println!("{}", rule);
}